九度 OJ 1463: 招聘會 - 貪心區間調度最大兼容子集

問題描述

有 n 場招聘會，每場有起止時間。一場結束瞬間另一場開始可參加。求最多能參加多少場。

貪心策略證明

按結束時間升序排序。依次選擇：當前最早結束且與已選不衝突的招聘會。
證明：最早結束的選擇留給後續最多可用時間，具備最優子結構與貪心選擇性質。

代碼

#include <bits/stdc++.h>
using namespace std;
struct Event { int s, e; };
bool cmp(Event a, Event b) { return a.e < b.e; }
int main() {
    int n;
    while (cin >> n) {
        vector a(n);
        for (auto &e : a) cin >> e.s >> e.e;
        sort(a.begin(), a.end(), cmp);
        int cnt = 0, lastEnd = -1;
        for (auto &e : a) {
            if (e.s >= lastEnd) {
                ++cnt;
                lastEnd = e.e;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}