貪婪區間排程（greedy interval scheduling）

你有一間會議室和一疊請求，每個請求要在固定的「開始—結束」時段使用房間。有些彼此重疊；你只能接受互不重疊的請求。目標是接待盡可能多的會議。直覺也許說抓最短的會議，或最早開始的——兩者都很誘人卻都錯。正確的貪婪規則是：在仍相容者中，永遠挑最早結束的會議。

演算法：把所有區間依結束時間排序；由左至右掃描；取第一個區間，然後對每個下一個區間，若其開始時間不早於你上一個取用區間的結束時間就取用，否則略過。如此而已——排序 O(n log n)、掃描 O(n)。為何「最早結束」正確：最早結束能盡快騰出房間，為其餘所有請求留下最多時間。這可由「貪婪始終領先」論證證明——在每個名次上，貪婪所選區間不晚於最佳選擇在該名次的區間結束，故貪婪能容納至少一樣多——也可由交換論證證明，把最佳解的第一個區間換成最早結束者。追蹤 {[1,3], [2,5], [4,7], [6,8]}：依結束排序，取 [1,3]，略過 [2,5]（重疊），取 [4,7]，略過 [6,8]——兩個會議，這裡為最佳。

由於證明極為乾淨，這是貪婪的經典首例，也是通往區間分割（使用多間房間）與最小化遲到的門戶。要內化的陷阱：那些顯而易見的替代方案是真的會失敗。最短優先可能挑一個小區間而擋住兩個較長且相容的區間；最早開始優先可能挑一個霸佔整條時間軸的長區間。只有最早結束優先有正確性證明。