問題描述

給定 N 個區間 [s_i, e_i]，選擇最少數量區間覆蓋 [1, T]。若無法覆蓋輸出 -1。N ≤ 25000。

貪心策略

1. 按區間起點 s 升序排序（s 相同時 e 降序）。
2. 維護 cur_end = 當前已覆蓋的最右端點，next_end = 下一步能達到的最右端點。
3. 遍歷區間：

• 若 s_i ≤ cur_end + 1（能接上），更新 next_end = max(next_end, e_i)。
• 否則（出現斷層）：
  若 next_end ≤ cur_end → 無法延伸，輸出 -1。
  否則：選擇上一輪的最佳區間，ans++，cur_end = next_end，重新考慮當前區間。

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;

struct Seg { int s, e; };
bool operator<(const Seg& a, const Seg& b) {
    return a.s < b.s || (a.s == b.s && a.e > b.e);
}

Seg seg[25005];

int main() {
    int n, T;
    while (~scanf("%d%d", &n, &T)) {
        for (int i=0;i 1) { puts("-1"); continue; }
        
        int ans = 1;
        int cur_end = seg[0].e;
        int next_end = seg[0].e;
        int i = 1;
        for (; i= T) break;
                --i; // 重新檢查當前區間
            }
        }
        if (ans != -1 && cur_end < T) {
            if (next_end >= T) ++ans;
            else ans = -1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵細節

1. 排序規則：s 升序、e 降序，保證同起點時優先考慮最長區間。
2. 斷層判斷：seg[i].s > cur_end + 1 表示無區間能接上 cur_end。
3. 回退 --i：更新 cur_end 後，當前區間可能已能接上新的 cur_end，需重新評估。
4. 結尾處理：循環結束後檢查是否已覆蓋 T，未覆蓋但 next_end 可達則再加一區間。

複雜度

• 時間：O(N log N) 排序 + O(N) 掃描。
• 空間：O(N)。

總結

POJ 2376 是「區間覆蓋」貪心的標準模板。核心不變量：cur_end 是已確定選擇區間覆蓋的最右端，next_end 是候選區間能達到的最右端。每當掃描到無法接上的區間，必須確定選擇一個區間（將 next_end 升級為 cur_end）。排序 + 單次掃描 + 回退檢查，構成完整貪心邏輯。注意邊界條件：起點必須 ≤ 1，結尾需額外判斷。