POJ 2376 Cleaning Shifts：區間覆蓋貪心選最少牛覆蓋全天

問題描述

N (≤ 25,000) 頭牛，每頭牛可工作區間 [s, e]。一天分 T (≤ 1,000,000) 個班次（1..T）。選最少牛使每個班次至少一頭牛工作（即區間並集覆蓋 [1, T]）。無解輸出 -1。

貪心策略：經典區間覆蓋

1. 按區間 起點升序、起點同則終點降序 排序。
2. 初始 curEnd = 0（已覆蓋到 0），ans = 0。
3. 當 curEnd < T：
   • 在所有 s ≤ curEnd + 1 的牛中，選 終點最大 的那頭（nextEnd）。
   • 若無此牛（nextEnd == curEnd） → 斷點，輸出 -1。
   • 否則 curEnd = nextEnd，ans++，繼續。
4. 輸出 ans。

為什麼這是最優？

每一步在「能接上已覆蓋區間」的候選中選擇延伸最遠的，這是區間覆蓋問題的標準貪心證明：任何最優解的第一個區間終點 ≤ 貪心選擇的終點，可替換不劣；遞歸同理。

代碼實現

#include 
using namespace std;
struct Cow { int s, e; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, T;
    if(!(cin >> N >> T)) return 0;
    vector cows(N);
    for (auto& c : cows) cin >> c.s >> c.e;
    sort(cows.begin(), cows.end(), [](const Cow& a, const Cow& b) {
        return a.s != b.s ? a.s < b.s : a.e > b.e;
    });
    int curEnd = 0, ans = 0, i = 0;
    while (curEnd < T) {
        int nextEnd = curEnd;
        while (i < N && cows[i].s <= curEnd + 1) {
            nextEnd = max(nextEnd, cows[i].e);
            i++;
        }
        if (nextEnd == curEnd) { cout << -1 << '\n'; return 0; }
        curEnd = nextEnd;
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

複雜度

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

關鍵細節

• 排序時終點降序：同起點下，長區間優先，避免短區間干擾選擇。
• 掃描指針 i 單調遞增，每頭牛只處理一次。
• 條件 cows[i].s <= curEnd + 1：班次為離散整數，覆蓋到 curEnd 後，下一班次為 curEnd+1，故起點需 ≤ curEnd+1。

總結

POJ 2376 是區間覆蓋貪心的教科書級例題。排序 + 單調掃描 + 選最遠延伸，代碼簡潔、證明嚴謹、複雜度優。掌握此模板可解決大類「最少區間覆蓋目標區間」問題。