Greedy — exchange argument proof technique: Visual walkthrough

We are going to prove one sentence:

The greedy schedule that runs the shortest job first minimises the total finishing time.

By the end you will see why, not just believe it.

Step 0 — The words before any symbol

Picture a single machine — a microwave, say. Only one job can run at a time. Each job has a length (how many seconds it needs). We line the jobs up in a queue and run them one after another, no gaps.

The difference between "length" and "completion time" is the whole story, so hold it tight: a 2-second job that starts at time 5 has length 2 but completion time 7.

Our goal — the thing we want as small as possible — is the sum of every job's finishing moment:

$total = \sum_{k} C_{k} add over all jobs k \sum when job k ends C_{k}$

Figure — Greedy — exchange argument proof technique

Step 1 — Why a job's ending time is a running total

WHAT. Look at three jobs on a timeline. The first job's finish is just its own length. The second job's finish is the first length plus its own. The third pays for the first two plus itself.

WHY. Because there are no gaps: each job starts exactly when the previous one ended. So a completion time is a prefix sum — it drags along everything that ran before it.

PICTURE. In the figure, follow the coral brackets: each finishing moment reaches back over all earlier lengths.

$C_{(1)} = p_{(1)}, C_{(2)} = p_{(1)} + p_{(2)}, C_{(3)} = p_{(1)} + p_{(2)} + p_{(3)}$

Here $p_{(1)}$ means "the length of whatever job we chose to run first", and so on — the parentheses say position in the queue, not job name.

Step 2 — Name the enemy: an inversion

To prove SPT (shortest-processing-time first) is best, we do not compare it against all schedules at once. Instead we hunt for one tiny local defect and squash it.

WHY this is the enemy. SPT means "shortest first" — which is exactly "no longer-before-shorter neighbours." So a schedule is the greedy one if and only if it has zero inversions. If we can prove every inversion can be removed without hurting the total, we can scrub a solution clean until it is greedy.

PICTURE. The red pair in the figure is an inversion: the tall coral block (long job $a$ ) blocks the short mint block (job $b$ ).

Step 3 — The swap, and why only two numbers change

WHAT. Take the inversion — neighbours $a$ then $b$ — and swap them: now $b$ runs first, then $a$ . Nothing else moves.

WHY only two numbers change. Everything scheduled before the pair is untouched, so their clocks are identical. Everything after the pair is also untouched — because the pair together still occupies the same total time $p_{a} + p_{b}$ , so later jobs start at the exact same moment as before. Only $C_{a}$ and $C_{b}$ can differ.

Let $t$ be the clock reading at the moment the pair starts (the letter $t$ = "time so far, before either of these two runs").

PICTURE. In the figure the grey region (before) and the striped region (after) are frozen; only the two coloured blocks trade places.

Before the swap (order $a$ then $b$ ):

$C_{a} = t + p_{a}, C_{b} = t + p_{a} + p_{b}$

$C_{a} = t + p_{a}$ : job $a$ finishes $p_{a}$ seconds after the pair started.
$C_{b} = t + p_{a} + p_{b}$ : job $b$ waits behind $a$ , so it pays $p_{a}$ then its own $p_{b}$ .

Step 4 — Add up both versions and subtract

WHAT. Compute the pair's contribution to the total in each order and compare.

Order $a$ then $b$ (the inversion):

$C_{a} + C_{b} = (t + p_{a}) + (t + p_{a} + p_{b}) = shared start 2 t + a counted twice 2 p_{a} + b once p_{b}$

Why is $p_{a}$ counted twice? Because job $a$ ran first, so $a$ 's length sits inside both completion times.

Order $b$ then $a$ (the fix):

$C_{b} + C_{a} = (t + p_{b}) + (t + p_{b} + p_{a}) = 2 t + 2 p_{b} + p_{a}$

WHY. Whoever goes first gets its length doubled. So to make the doubled term small, we want the shorter job first.

PICTURE. The figure stacks the two totals as bar heights; the difference is a single mint sliver.

Subtract the fixed order from the broken one:

$cost(inversion) - cost(fixed) = (2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = > 0 since p_{a} > p_{b} p_{a} - p_{b}$

Step 5 — From one swap to the whole proof

WHAT. We just showed: any schedule containing an inversion is not optimal, because we can strictly improve it.

WHY that finishes everything. Suppose the optimal schedule $O$ had an inversion. Then $Δ > 0$ lets us build a strictly cheaper schedule — contradiction, since $O$ was supposed to be the best. So the optimal schedule has no inversions. But "no inversions" is exactly the definition of the greedy SPT order. Therefore SPT is optimal. This is a proof by contradiction resting on the swap.

PICTURE. The chain: start from any $O$ , remove inversions one by one (each arrow a swap that never raises cost), and you slide down to $G$ , the fully sorted greedy schedule.

$O = O_{0} \to O_{1} \to \dots \to O_{m} = G, cost (O_{i + 1}) \leq cost (O_{i})$

Step 6 — The degenerate and edge cases (never skip these)

Definition Cases we must check

Equal lengths $p_{a} = p_{b}$ : then $Δ = p_{a} - p_{b} = 0$ . The swap changes nothing — both orders are equally good. Greedy is still an optimal order; it's just not the unique one. No contradiction, no problem.
One job ( $n = 1$ ): no neighbours, no inversion possible, greedy trivially optimal.
Zero-length job $p_{k} = 0$ : it adds its own $C_{k}$ but never delays anyone. SPT puts it first (shortest), which is correct — an instant job should never block others.
All lengths equal: every order gives the identical total; the "no worse" (not "strictly better") version of the argument still holds — see the contrast with activity selection, where the swap is always equal-cost.
Weighted version $\sum w_{k} C_{k}$ : the swap now gives $Δ = w_{b} p_{a} - w_{a} p_{b}$ , which is $\geq 0$ exactly when $p_{a} / w_{a} \geq p_{b} / w_{b}$ — so you must sort by the ratio $p_{k} / w_{k}$ (Smith's rule), not by length. Setting every $w_{k} = 1$ recovers our plain SPT.

The one-picture summary

Everything above compresses into one image: a broken schedule (an inversion), the swap arrow, and the strictly-shorter total bar it produces — with the chain sliding down to the sorted greedy schedule at the bottom.

Recall Feynman: the whole walkthrough in plain words

Imagine kids using one microwave, and we care about the total of everyone's finishing times added up. A job that runs early makes everybody behind it wait longer, so its length gets counted again and again. That means a long job up front is a disaster. Now suppose you found the supposedly best line-up and spotted a tall kid standing right in front of a short kid — swap them! The two of them together still take the same total time, so nobody else's clock moves. But now the short kid finishes early and only the short length gets counted twice instead of the long one — so the grand total drops. Since the "best" line-up could be improved, it wasn't really the best. The only line-ups you can't improve this way are the ones with no tall-before-short pairs — which is exactly "shortest first." So shortest-first wins. That single swap, repeated until nothing is left to fix, is the entire exchange argument.

Recall Self-check

What does $C_{k}$ measure — length or finishing moment? ::: The finishing moment (wall-clock time the job ends), which is a prefix sum of all lengths up to and including it. Why does the $2 t$ term cancel in the swap? ::: Both orders start the pair at the same clock reading $t$ , so the shared-start contribution is identical and drops out of the difference. What is $Δ$ for the unweighted swap, and its sign? ::: $Δ = p_{a} - p_{b}$ , strictly positive whenever $a$ (longer) precedes $b$ (shorter), proving the inversion is beatable. What replaces $Δ$ in the weighted case? ::: $Δ = w_{b} p_{a} - w_{a} p_{b} \geq 0 ⟺ p_{a} / w_{a} \geq p_{b} / w_{b}$ , giving Smith's rule.

Connected notes: parent topic · Greedy Algorithms — general paradigm · Greedy-stays-ahead proof technique · Scheduling to minimise completion time · Smith's rule — weighted completion time · Activity Selection Problem · Huffman Coding · Proof by contradiction · Induction · Matroids and the greedy theorem · Dynamic Programming