题解 | #活动安排# ✅✅✅ 经典贪心满分题解

关键词：贪心算法

核心思想：通过优先选择结束时间最早且与前一个选定活动不冲突的活动，来最大化可以安排的活动数量。

解题步骤：

1. 将所有活动按结束时间升序排序。
2. 遍历每个活动，对于一个活动，如果它的开始时间晚于或等于上一个选中活动的结束时间，则安排此活动。

复杂度：时间复杂度O(nlogn)，空间复杂度O(n)。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// 定义活动类型，相当于给pair<int, int>起了别名Activity，用于保存活动起始和结束时间
using Activity = pair<int, int>;

// 比较函数，用于排序活动，按照结束时间升序
bool compareActivities(const Activity &a, const Activity &b) {
    return a.second < b.second;
}

int main() {
    int n;
    cin >> n;
    vector<Activity> activities(n);
    for (Activity &act : activities)  cin >> act.first >> act.second;
  
    // 按照活动的结束时间进行排序
    sort(activities.begin(), activities.end(), compareActivities);

    int ans = 0;
    int lastEndTime = -1; // 上一个活动结束时间初始化为-1
    for (Activity act : activities) 
        if (act.first >= lastEndTime) { // 如果当前活动开始于上一个活动结束后
            ++ans;   // 安排活动数+1
            lastEndTime = act.second;    // 更新最后活动的结束时间
        }

    cout << ans << endl; 
    return 0;
}