【例85.2】 区间调度问题

解题思路

活动按结束时间升序排序，每次选择起始时间不早于上一活动结束的活动，选择后更新可用时间。

正确性说明

结束最早的活动可替换任意最优解的第一个活动，且不会妨碍后续活动。反复对剩余活动应用此交换论证，得到贪心可达到最多数量。

易错点

结束时可立即开始下一活动，用>=；初始时间用最小值兼容0起点。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (auto &p : a)
        cin >> p.second >> p.first;
    sort(a.begin(), a.end());
    int end = INT_MIN, count = 0;
    for (auto p : a)
        if (p.second >= end) {
            count++;
            end = p.first;
        }
    cout << count << "\n";
    return 0;
}