POJ 3190 Stall Reservations 區間調度與最小資源分配

問題模型

N (≤ 50,000) 頭牛，每頭有專屬擠奶區間 [A, B]（含端點）。同一欄位同一時間只能容納一頭牛。求最少欄位數，並輸出每頭牛的欄位分配方案（任意合法解均可）。

經典轉化：區間圖著色 = 最大重疊數

將區間按起始時間升序排序。維護一個**最小堆**，堆頂保存各欄位當前最後結束時間。遍歷區間：

1. 若堆非空且堆頂 ≤ 當前區間起點，說明該欄位已釋放，彈出並重用該欄位。
2. 否則需新增欄位（堆大小 +1）。
3. 將當前區間結束時間與分配的欄位編號推入堆。

遍歷結束時堆的最大尺寸即為答案。同時記錄每頭牛獲得的欄位號即可輸出方案。

關鍵細節

• 區間端點**包含關係**：[2,4] 與 [4,6] **衝突**（時刻 4 重疊），故判斷條件為 heap.top().end < cur.start（嚴格小於）。
• 輸出需保持原輸入順序，故排序前保存原索引。
• 欄位編號從 1 開始分配，複用時沿用原編號。

參考代碼 (C++)

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

struct Cow {
    int s, e, id;
    bool operator<(const Cow& o) const { return s < o.s; }
};

struct Stall {
    int end, idx;
    bool operator>(const Stall& o) const { return end > o.end; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;  cin >> N;
    vector cows(N);
    for (int i = 0; i < N; ++i) {
        cin >> cows[i].s >> cows[i].e;
        cows[i].id = i;
    }
    sort(cows.begin(), cows.end());

    priority_queue, greater> pq;
    vector assign(N);
    int maxStalls = 0, nextStall = 1;

    for (const auto& c : cows) {
        if (!pq.empty() && pq.top().end < c.s) {
            // 復用欄位
            Stall cur = pq.top(); pq.pop();
            cur.end = c.e;
            assign[c.id] = cur.idx;
            pq.push(cur);
        } else {
            // 新欄位
            assign[c.id] = nextStall;
            pq.push({c.e, nextStall});
            ++nextStall;
        }
        maxStalls = max(maxStalls, (int)pq.size());
    }

    cout << maxStalls << "\n";
    for (int x : assign) cout << x << "\n";
    return 0;
}

複雜度分析

• 排序 O(N log N)，堆操作 O(N log N)，總時間 O(N log N)。
• 空間 O(N)。