問題：一間教室，不准重疊
想像只有一間講堂，以及一疊使用它的請求。每個請求是一個區間，有開始時間與結束時間——比方說 [9, 10]、[9:30, 11]、[10, 11:30] 等等。若兩個請求的區間重疊，它們就衝突。只要被接受的請求兩兩不重疊，你可以接受任意一組請求，而你的目標是接受愈多愈好。這就是區間排程，一個教科書級的最佳化問題：在所有合法（無衝突）的選法中，我們要規模最大的那一個。
注意我們在數什麼。我們要的是最多的請求數，不是最多的房間使用時數——每個被接受的區間都只算一個，無論它持續十分鐘或三小時。這個區別很重要，因為它悄悄排除了所有誘惑中最大的那個啟發法。暴力法那一階會列舉請求的每個子集、留下最大的無衝突者來解這題，但 n 個請求有 2^n 個子集——慢得無望。貪婪法承諾遠勝於此：排序一次、掃過一遍，當場為每個請求做決定。
哪一條貪婪規則？三條失敗的，一條成功的
貪婪意味著我們固定一個順序，照那個順序走過請求，若某個請求不與已接受者衝突就接受它。唯一真正的決定是設定順序的那條規則。有好幾條規則聽起來都合理。最早開始時間——誰先提出就先抓？這會失敗：一個 9:00 開始卻撐到 18:00 的請求霸佔整天，擋掉幾十個短的。最短區間——挑最簡短的請求，好塞進更多？這也失敗：一個卡在兩個較長請求之間的 30 分鐘請求，可能同時撞掉那兩個，而保留那兩個本來更好。
最少衝突——挑與其他人重疊最少的請求，盼著留下最多空間？這是其中聽起來最聰明的一條，但在精心建構的例子上它仍會失敗。真正有效的規則簡單到近乎令人尷尬：最早結束時間優先。把所有請求依結束時間排序，然後由左往右掃，每當某個請求的開始不早於你上一個接受者的結束時，就接受它。這份直覺是誠實的、值得記牢：最早把房間騰出來的請求，為後面的一切留下最多時間。 在所有你可以先拿的請求中，最早結束的那個對未來最慷慨。
一個小小的追蹤
在五個請求上跑一次最早結束時間。依結束時間排序得到下面的順序；我們掃一遍，維護一個滾動的「上次結束」，並接受任何開始時間不早於它的請求。
requests sorted by finish: A[1,4] B[3,5] C[0,6] D[5,7] E[6,8]
last_finish = -inf
A: starts 1 >= -inf -> ACCEPT, last_finish = 4
B: starts 3 < 4 -> skip (overlaps A)
C: starts 0 < 4 -> skip (overlaps A)
D: starts 5 >= 4 -> ACCEPT, last_finish = 7
E: starts 6 < 7 -> skip (overlaps D)
chosen = { A, D } size 2 (optimal here)從這個追蹤帶走兩件事。第一，工作不過是一次排序加上一趟線性掃描，所以整個演算法跑在 O(n log n)——排序主宰一切，那是線性對數時間，比起 2^n 是一次巨大的下墜。第二，注意 C[0,6] 這個最長的請求很早就被丟掉了：貪婪法甚至不曾認真考慮它，因為 A 結束得更早、為 D 清出了路。請求的長度無關緊要；只有它的結束時間在掌舵。
為什麼它最佳：貪婪一路領先
一個追蹤顯示這條規則在一個例子上獲勝；它沒顯示它「總是」獲勝。要做到那點我們需要證明，而這裡的證明技巧有個好記的名字：貪婪一路領先。其構想是把貪婪的執行過程一個請求接一個請求地，拿來和「任一個」最佳解比較，並證明貪婪從未落後。設貪婪挑出 g1、g2、g3、…（依它接受的順序），並設某個最佳解挑出 o1、o2、o3、…——兩串都依結束時間排序。我們要證明一個乾淨的不變量：對每個 k，貪婪的第 k 個被接受的請求結束的時間不晚於最佳解的第 k 個，亦即 finish(g_k) <= finish(o_k)。
- 基底情形（k = 1）：貪婪的第一個選擇，依其規則，是全部請求中結束時間最早的那個。所以沒有任何請求能比 g1 更早結束——尤其 finish(g1) <= finish(o1)。貪婪起步時（至少）打平。
- 歸納步驟：假設 finish(g_k) <= finish(o_k)。最佳解的下一個請求 o_{k+1} 在 o_k 結束之後才開始，因此（由假設）也在 g_k 結束之後才開始。所以當貪婪選 g_{k+1} 時，o_{k+1} 是一個合法的候選——它不與貪婪已接受的任何東西衝突。
- 在那一刻所有合法候選中，貪婪挑結束最早的那個。既然 o_{k+1} 是合法的，貪婪的選擇結束的時間不晚於它：finish(g_{k+1}) <= finish(o_{k+1})。不變量便從 k 傳遞到 k+1。
- 用反證收尾：假設最佳解接受的請求比貪婪多，於是它有一個 o_{m+1}，而貪婪停在 g_m。由不變量 finish(g_m) <= finish(o_m)，且 o_{m+1} 在 o_m 之後才開始，所以 o_{m+1} 對貪婪而言仍是合法的——貪婪本會拿下它而不停手。矛盾。所以貪婪接受的數量至少和最佳解一樣多，因而恰好一樣多：它是最佳的。
看看這個論證的形狀：它正是一個迴圈不變量用歸納法證出來的，與你在正確性那一階見過的同一套機制——只是現在不變量說的是「貪婪領先」，而非「陣列已部分排序」。這也是我們第一次具體目睹貪婪選擇性質：宣稱採取局部最佳的一步（最早結束）絕不會把全域最佳解擋在門外。證明正是讓那個宣稱站得住腳的東西；沒有它，那性質只是個願望。
一個表親問題，與一條誠實的邊界
把問題稍微一改，新的貪婪法就出現了。假設我們必須排進所有請求，但可以開更多房間；我們要最少的房間數，使得任何房間都不會被重複預訂。那是區間劃分。這裡正確的規則依開始時間排序，掃過時把每個請求指派給任何空閒的房間，只在沒有空房時才開一間新的。它開的房間數，等於任一瞬間重疊區間的最大數目——這個量叫做深度——而你顯然不可能做得比深度更好，因為那麼多請求是真的同時發生。同樣是區間的領域、不同的目標、不同的貪婪法，但證明的味道相同：證明貪婪的數量達到一個無法被打敗的下界。
兩個收尾的提醒讓我們保持誠實。O(n log n) 的成本是漸進的：對少少幾個請求，排序的開銷是真實的，一個笨方法或許還能與它打平，但隨著 n 變大，貪婪法把 2^n 的列舉遠遠甩在身後。而且要記得，「一路領先」證明的優雅完全建立在不帶權的目標上；它是某一種貪婪論證形狀的範本，不是萬能鑰匙。它的搭檔技巧——交換論證——能處理許多「一路領先」處理不了的情形，而下一篇指南正是專講它的。