the 'greedy stays ahead' argument

Picture two runners on the same track: greedy and any rival optimal solution. Instead of editing the rival to look like greedy (the exchange argument), you show that after every step greedy is at least as far along as the rival on some measured quantity. If greedy never falls behind, it cannot finish worse — so it is optimal. That is the 'greedy stays ahead' proof.

Concretely you pick a measure that compares greedy's partial solution to the optimal one step by step, then prove by induction that greedy is always ahead by that measure. Take interval scheduling. Let greedy's chosen jobs, sorted by finish time, be g1, g2, g3, ... and some optimal selection be o1, o2, o3, .... Claim: for every r, the finish time of greedy's r-th job is no later than the finish time of the optimal's r-th job. Base case: greedy first picks the globally earliest-finishing job, so g1 finishes no later than o1. Inductive step: since greedy's first r-1 jobs finish no later than the optimal's, the r-th optimal job is available to greedy too (it starts after gr-1 finishes), and greedy picks the earliest-finishing available job, so gr finishes no later than or. Because greedy never finishes later at any rank, it can never run out of room early, so it schedules at least as many jobs as the optimal — hence exactly as many.

Staying-ahead and exchange arguments are the two standard ways to prove greedy correctness, and often either works. Staying-ahead shines when there is a natural running quantity to compare (finish times, cumulative cost, prefix length). The discipline that matters: you must define the comparison measure explicitly and prove the lead is maintained at every step by induction — a vague 'greedy is always better' is not a proof, it is a wish.