HDU 2037：今年暑假不 AC (貪心區間調度)

問題描述

經典活動安排問題：給定 n 個活動，各有開始/結束時間。選最大兼容子集（不重疊）。多測試案例，n=0 結束。

貪心策略：按結束時間升序

證明：最早結束的活動留給後續最多空間。算法：

1. 按結束時間排序（結束時間相同可按開始時間排序）。
2. 選第一個活動，記錄其結束時間 last_end。
3. 遍歷剩餘活動，若開始時間 ≥ last_end，選中，更新 last_end。

參考代碼 (C++)

#include 
using namespace std;
struct Act { int s, e; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n, n) {
        vector a(n);
        for (auto &x : a) cin >> x.s >> x.e;
        sort(a.begin(), a.end(), [](Act &a, Act &b) {
            return a.e < b.e || (a.e == b.e && a.s < b.s);
        });
        int cnt = 0, last = -1;
        for (auto &x : a) if (x.s >= last) {
            ++cnt;
            last = x.e;
        }
        cout << cnt << '\n';
    }
    return 0;
}

複雜度

排序 O(n log n)，掃描 O(n)。n ≤ 100 瞬間完成。

關鍵點

• 區間調度貪心算法教科書級例題。
• 按**結束時間**排序是核心，按開始時間或長度均不正確。
• 多測試案例以 n=0 結束，注意讀入邊界。

總結

• 最經典的貪心算法之一，必須熟練掌握證明與實現。
• 代碼極短，邊界情況少，適合作為模板背誦。
• 擴展：帶權重區間調度需 DP，無權重貪心最優。