Proving a Greedy Rule Optimal by Exchange

The problem: an interviewer asks you to schedule jobs to minimize average waiting time, and you correctly guess the rule is "always run the shortest job first." Guessing the right rule is only half the answer — they'll then ask why it's optimal. Just saying "it feels right" won't do. Exchange argument is the standard technique for proving a greedy ordering rule is truly optimal, and it's short enough to write out on a whiteboard in under a minute once you know the pattern.

The technique in words

Take any valid ordering that disagrees with your greedy rule somewhere — meaning two adjacent items are in the "wrong" relative order. Swap just those two adjacent items. Show that the swap never makes the objective worse (and sometimes makes it strictly better). Since any ordering can be transformed into the greedy ordering through a sequence of such adjacent swaps, and none of those swaps ever hurts, the greedy ordering must be at least as good as every other ordering — hence optimal. The whole proof lives in analyzing one swap, not the entire schedule.

Worked example: shortest-job-first minimizes average wait

Jobs have processing times $p_1, \dots, p_n$ and everyone waits in a single queue; a job's wait time is the sum of processing times of all jobs ahead of it. Suppose an ordering has two adjacent jobs $A$ then $B$ with $p_A > p_B$ (a longer job scheduled before a shorter one — the "wrong" order under shortest-job-first). Every job before $A$ and after $B$ has an unchanged wait time, since the swap doesn't move them. Only $A$ and $B$'s own waits change:

• Before the swap: $B$ waits for $A$ to finish, so $B$'s wait includes $p_A$; $A$'s wait doesn't include $p_B$.
• After swapping to $B$ then $A$: $A$'s wait now includes $p_B$; $B$'s wait no longer includes $p_A$.

The combined wait for the pair goes from (whatever came before) $+ p_A$ (for $B$) to (whatever came before) $+ p_B$ (for $A$). Since $p_A > p_B$, swapping strictly decreases the combined wait time of this pair, and touches nothing else. Repeating this swap on every adjacent "wrong-order" pair, sorted-by-length order is reached, and every step along the way only decreased total wait — so no other ordering can beat shortest-job-first.

Worked example 2: earliest-finish-time for interval scheduling

The same skeleton proves the greedy rule for maximizing non-overlapping jobs picked from a set of intervals ("always take the job that finishes earliest among those still available"): compare the greedy choice's finish time to any other valid first choice, note the greedy choice's finish time is by definition no later, so swapping it in can only free up more room for later choices, never less. The exchange argument here swaps which interval is chosen first, rather than swapping two positions in a queue, but the shape of the proof — one local swap, show it's never worse — is identical.

What this means in practice

Exchange argument is the go-to proof whenever a problem's optimal solution is some ordering or selection and you suspect a simple local rule (shortest first, earliest deadline first, highest ratio first) governs it. It's also a useful sanity check on your own greedy code: if you can't find a swap that provably doesn't hurt, your greedy rule is probably wrong, and you should look for a counterexample before writing it up.