题解 | 活动安排（经典贪心）

#牛客春招刷题训练营# + 链接

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

1.将所有活动按结束时间升序排序。

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

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

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

using PII = pair<int,int>;
const int MAXN=200010;
PII a[MAXN];

bool cmp(const PII& p, const PII& q) {
    return p.second<q.second;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++) {
        scanf("%d%d", &a[i].first, &a[i].second);
    }
    sort(a+1,a+n+1,cmp);
    int ans=0, pre=-1;
    for (int i=1;i<=n;i++) {
        if (a[i].first>=pre) {
            ++ans;
            pre = a[i].second;
        }
    }
    printf("%d\n", ans);
    return 0;
}