區間分割（interval partitioning）

現在把區間問題反過來。不是一間房間裝下盡可能多的講座，而是你必須排定「所有」講座，每個都在某間房間，且任兩個重疊的講座不共用房間——而你想用「最少」的房間。想想全都必須舉行的課程；課表至少需要幾間教室？

先有一個漂亮的下界：在任一瞬間，數一數該時刻有多少區間正在進行（活躍）；這類計數的最大值稱為深度。你顯然至少需要「深度」間房間，因為那麼多講座確實在某一點重疊，每個都需要自己的房間。貪婪演算法恰好達到這個界。把區間依開始時間排序；逐一掃過；對每個區間，把它指派給任何目前空閒的房間（其上一場講座已結束）；若無空閒房間，就開一間新房間。證明這用恰好「深度」間房間：只有當一個區間開始且所有現有房間都忙碌時才開新房間，意味著那些房間加上新房間同時活躍——故當你開第 k 間房間時，有 k 個重疊區間，因此深度至少為 k。貪婪開的房間從不超過深度所迫，也從不少於所需，故為最佳。以房間空閒時間為鍵的最小堆積實作，此演算法為 O(n log n)。

區間分割等同於用最少顏色為一個區間圖著色，是貪婪恰好達到可證下界的乾淨案例。值得記住的重點：深度（最大同時重疊數）就是答案，而貪婪掃描只是達成它的高效、構造性方法。常見錯誤是像單房間問題那樣依結束時間排序——分割問題你必須依「開始」時間排序，才能按區間開始的順序處理它們。