「貪婪始終領先」論證（greedy stays ahead）

想像同一條跑道上有兩名跑者：貪婪，以及任何一個對手最佳解。你不去把對手改寫成貪婪的樣子（那是交換論證），而是說明每一步之後，在某個被測量的量上貪婪至少和對手一樣前進。若貪婪從不落後，它就不可能結束得更差——故為最佳。這就是「貪婪始終領先」的證明。

具體上你挑一個量，把貪婪的部分解與最佳解逐步比較，再用歸納法證明貪婪在該量上始終領先。以區間排程為例。令貪婪所選的工作按結束時間排序為 g1, g2, g3, ...，某個最佳選擇為 o1, o2, o3, ...。主張：對每個 r，貪婪第 r 個工作的結束時間不晚於最佳第 r 個工作的結束時間。基底：貪婪先挑全域最早結束的工作，故 g1 不晚於 o1 結束。歸納步：既然貪婪前 r-1 個工作都不晚於最佳的結束，最佳的第 r 個工作對貪婪也可用（它在 gr-1 結束後才開始），而貪婪挑最早結束的可用工作，故 gr 不晚於 or 結束。因為貪婪在任何名次都不更晚結束，它就不會提早用盡空間，故安排的工作數至少和最佳一樣多——因此恰好一樣多。

領先論證與交換論證是證明貪婪正確性的兩種標準方法，往往兩者皆可。當有一個自然的累進量可比較時（結束時間、累計成本、前綴長度），領先論證最出色。要緊的紀律：你必須明確定義比較的量，並以歸納法證明每一步都維持領先——含糊的「貪婪總是比較好」不是證明，只是願望。