活动安排

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 805 字

按结束时间排序贪心选最多不相交区间

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1422
// 题意：n 个活动各占用区间 [si, fi]，同一资源只能同时供一个活动使用，求最多能安排多少个互不重叠的活动。
// 思路：按结束时间升序排序后贪心扫描。
// 1. 结束越早的活动，留给后面的时间越多，所以优先选它。
// 2. 只要当前活动的开始时间不早于上一个选中活动的结束时间，就选进来。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：端点相接（前一个的 fi 恰好等于后一个的 si）不算重叠，判断必须用 >= 而不是 >。
// 易错点：排序关键字是结束时间 fi，不是开始时间 si。
#include <bits/stdc++.h>
using namespace std;
struct Act {
    int s, f;
};
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<Act> a(n);
    for(int i = 0; i < n; i++) cin >> a[i].s >> a[i].f;
    sort(a.begin(), a.end(), [](const Act& x, const Act& y){
        return x.f < y.f;
    });
    int ans = 0;
    int last = 0;
    for(int i = 0; i < n; i++){
        if(a[i].s >= last){
            ans++;
            last = a[i].f;
        }
    }
    cout << ans << "\n";
    return 0;
}

活动安排

正文

一本通·提高篇的其它内容