貪心演算法經典：區間排程 / 最大不重疊線段數 (Activity Selection) 完整解析與 AC 代碼

問題描述

給定 N 條線段 (起點 S, 終點 E)，選出最多條件為兩兩不重疊的線段數量。N ≤ 10000，座標範圍 ±1e9。

貪心策略證明

「優先選擇終點最早的線段，再從剩餘中繼續選擇終點最早且起點 ≥ 上一條終點的線段」可得到最優解。

證明核心：交換論證。任何最優解若第一條線段非最早結束，可替換為最早結束者而不減少總數。

演算法步驟

1. 依終點 `E` 遞增排序 (若相同，起點 `S` 遞增)。
2. `cnt = 1`，`lastEnd = seg[0].E`。
3. 遍歷 `i = 1 .. N-1`：
   • 若 `seg[i].S >= lastEnd`：`cnt++`，`lastEnd = seg[i].E`。
4. 輸出 `cnt`。

時間複雜度

排序 `O(N log N)`，掃描 `O(N)`，總 `O(N log N)`，滿足 N=10000。

完整 AC 代碼 (C++17)

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

struct Seg { long long s, e; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N) {
        vector a(N);
        for (int i = 0; i < N; ++i) cin >> a[i].s >> a[i].e;
        sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) {
            return x.e < y.e || (x.e == y.e && x.s < y.s);
        });
        int ans = 0;
        long long last = LLONG_MIN;
        for (const auto& seg : a) {
            if (seg.s >= last) {
                ++ans;
                last = seg.e;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

常見 WA 原因

• 排序鍵值錯誤（依起點排序、或未處理終點相同時起點順序）。
• 判斷條件用 `>` 而非 `>=`（端點相接視為不重疊）。
• 未使用 `long long` 導致座標溢位。
• 輸入測資多組但未迴圈讀取至 EOF。

延伸變體

• 帶權重區間排程 → DP + 二分搜 `O(N log N)`。
• 多機器/資源區間排程 → 最小堆維護資源釋放時間 `O(N log K)`。
• 圓環區間 → 複製陣列展開或枚舉起點。