Greedy — exchange argument proof technique: Worked examples

You have seen the recipe in the parent note (3.7.3). This page is the drill hall: we march through every kind of situation an exchange argument can face, so that when a new problem lands on your desk you already recognise its shape.

Before any symbol is used, here is the notation the whole page uses, in plain words:

Definition The sequence notation

$g_{i}$ , $o_{i}$ , and what "inversion" means

$O$ = any optimal solution (achieves the best possible score).
$G$ = the solution greedy builds.
We write both as ordered lists: $G = (g_{1}, g_{2}, \dots, g_{n})$ and $O = (o_{1}, o_{2}, \dots, o_{n})$ . Here $g_{i}$ = greedy's $i$ -th choice in order (so $g_{1}$ is greedy's very first pick), and $o_{i}$ = the element sitting in position $i$ of the optimal solution $O$ . The subscript is just the slot number, counting from $1$ .
An inversion in $O$ is a pair of positions $i < j$ where $o_{i}$ and $o_{j}$ are in the opposite order to greedy's sorting rule — i.e. greedy's key says $o_{j}$ should come before $o_{i}$ , yet $O$ puts $o_{i}$ first. An adjacent inversion is the special case $j = i + 1$ (the two offending elements are neighbours). To find one: scan $O$ left to right and stop at the first position $i$ where $o_{i}$ 's key is "later" than $o_{i + 1}$ 's key.

Recall Two facts we reuse everywhere (recapped so this page stands alone)

Completion time. If jobs run one at a time, a job's finish time $C_{k}$ = its start plus the total length of everything run up to and including it. The unweighted total completion time is $\sum_{k} C_{k}$ .
The adjacent-swap identity for $\sum C_{k}$ . Suppose two adjacent jobs $a$ (first) then $b$ start at time $t$ . Then $C_{a} = t + p_{a}$ and $C_{b} = t + p_{a} + p_{b}$ , so their combined contribution is $(t + p_{a}) + (t + p_{a} + p_{b}) = 2 t + 2 p_{a} + p_{b}$ . Swap them and it becomes $2 t + 2 p_{b} + p_{a}$ . The whole schedule cost changes only in these two terms, so with $Δ = cost (O) - cost (O^{'})$ the difference of the swap is $(2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = p_{a} - p_{b}$ . Longer-first before shorter costs more by exactly $p_{a} - p_{b}$ .

The scenario matrix

Every cell below is a distinct behaviour an exchange swap can show. The Cell column is a letter ID ( $A$ – $I$ ) we refer to as "cell A", "cell B", etc.; each worked example is tagged with the cell it covers.

Cell	Scenario class	What the swap does to cost	Example
A	Strict improvement (minimisation)	$Δ > 0$ : cost strictly drops → contradiction	Ex 1
B	Equal cost (counting / maximisation)	$Δ = 0$ : cost unchanged → still optimal	Ex 2
C	Ratio / weighted objective	sign of $Δ$ set by a ratio rule	Ex 3
D	Two-swap construction	must sum both terms	Ex 4
E	Degenerate input (ties, equal keys)	$Δ = 0$ , greedy still fine	Ex 5
F	Zero / empty / single element	base case, no swap possible	Ex 6
G	Where greedy FAILS (no exchange lemma)	swap can increase cost ( $Δ < 0$ )	Ex 7
H	Real-world word problem	translate to A or C	Ex 8
I	Exam twist (non-adjacent swap, prove chain)	swap far-apart items	Ex 9

Prerequisites you may want open: Proof by contradiction, Induction, Greedy Algorithms — general paradigm.

Example 1 — Strict improvement (cell A)

Worked example Adjacent inversion in SPT, with numbers

Statement. Two jobs, lengths $p_{a} = 7$ , $p_{b} = 3$ , both start at time $t = 4$ . An optimal-looking schedule runs the long job $a$ first. Show swapping gives a strictly smaller total completion time $\sum C_{k}$ , and by how much.

Forecast: guess — will the total drop, and does the drop equal $7 - 3$ ?

Compute the "long-first" order. $C_{a} = t + p_{a} = 4 + 7 = 11$ . Then $C_{b} = t + p_{a} + p_{b} = 4 + 7 + 3 = 14$ . Sum $= 25$ . This is the order with an adjacent inversion: positions $i = 1, j = 2$ hold $o_{1} = a$ (long) before $o_{2} = b$ (short), the opposite of SPT's "short first." Why this step? The finish time of a job is its start plus everything run up to and including it; the second job waits for the first.
Compute the "short-first" order $O^{'}$ . $C_{b} = t + p_{b} = 4 + 3 = 7$ . Then $C_{a} = 4 + 3 + 7 = 14$ . Sum $= 21$ . Why this step? Swapping only reorders the pair; jobs outside the pair are untouched, so only these two terms move.
Difference. $Δ = cost (O) - cost (O^{'}) = 25 - 21 = 4 = p_{a} - p_{b}$ . Why this step? Using the recapped adjacent-swap identity, the two orders contribute $2 t + 2 p_{a} + p_{b}$ (long first) vs $2 t + 2 p_{b} + p_{a}$ (short first). The $2 t$ cancels, leaving the gap $(2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = p_{a} - p_{b}$ — the job that finishes second pays the other's length, so putting the shorter job first shrinks the doubled term.

Verify: $p_{a} - p_{b} = 7 - 3 = 4$ . ✅ Matches the direct sum $25 - 21$ . Units: time-units; the shorter-first order saves 4 time-units of waiting. Because $Δ > 0$ strictly, "long-first" cannot be optimal — cell A.

Example 2 — Equal cost (cell B)

Worked example Activity selection: swap the first pick, count stays equal

Statement. Activities (start, finish): $A = [1, 4)$ , $B = [3, 5)$ , $C = [0, 6)$ , $D = [5, 7)$ , $E = [6, 8)$ . Pick the maximum number of non-overlapping intervals. Test the exchange with greedy's first pick.

Forecast: greedy picks the earliest-finishing activity. Which is it, and will replacing an optimal pick with it keep the count the same?

The figure below draws all five intervals as horizontal bars on a time axis; use it to see the swap.

Figure (alt-text). Five horizontal bars on a time axis (0 to 8). Bar $A$ spans time 1–4 (orange), $B$ spans 3–5 (plum), $C$ spans 0–6 (grey), $D$ spans 5–7 (teal), $E$ spans 6–8 (grey). An orange dashed vertical line at time 4 marks where $A$ finishes; a label notes that $D$ starts at 5, so $D$ still fits after $A$ . An orange arrow points at $A$ ("greedy g1 = earliest finish 4") and a plum arrow shows the swap $B \to A$ keeping the count at 2.

Recall the notation: $g_{1}$ = greedy's first choice, and $o_{1}$ = the element in position 1 of the optimal list $O$ (here $O$ is written in finish-time order).

Find greedy's first pick $g_{1}$ . Finish times: $A : 4, B : 5, C : 6, D : 7, E : 8$ . Earliest finish is $A$ (finish $4$ ). So $g_{1} = A$ — the orange bar in the figure. Why this step? Greedy's rule for Activity Selection Problem is "earliest finish among compatible."
Take an optimal solution. Maximum non-overlapping count here is $2$ , e.g. $O = {A, D}$ or $O = {B, D}$ or $O = {B, E}$ . Take $O = (B, D)$ (does not contain $A$ ), so $o_{1} = B$ , $o_{2} = D$ . Why this step? We need an optimal $O$ that disagrees with greedy on the first pick to demonstrate the swap.
Swap $o_{1} = B$ for $g_{1} = A$ . In the figure, $A$ finishes at $4 \leq 5 =$ finish of $B$ . The next chosen activity $D = [5, 7)$ starts at $5 > 4$ (right of the dashed line), so it is still compatible. New set $O^{'} = (A, D)$ , size $2$ . Why this step? $g_{1}$ finishes no later than $o_{1}$ , so anything that fit after $o_{1}$ still fits after $g_{1}$ — feasibility preserved. (An exchange proof always has two obligations: the result is still legal and no worse.)

Verify: $∣ O^{'} ∣ = 2 = ∣ O ∣$ , so $Δ = cost (O) - cost (O^{'}) = 0$ . ✅ Same count — a maximisation/counting problem gives $Δ = 0$ (cell B), and $O^{'}$ now agrees with greedy on pick 1. Sanity: no two intervals in ${A, D}$ overlap since $4 \leq 5$ (visible as no bar-overlap across the dashed line).

Example 3 — Ratio / weighted objective (cell C)

Worked example Smith's rule decides who goes first

Statement. Two jobs, $(p_{a}, w_{a}) = (6, 2)$ and $(p_{b}, w_{b}) = (2, 3)$ , weighted objective $\sum w_{k} C_{k}$ , both starting at $t = 0$ . Which order is optimal, and what is the cost change of an adjacent swap?

Forecast: SPT says "shorter first" ⇒ $b$ first (length 2). But weights matter — guess whether ratio $p / w$ agrees.

Recap of the rule we lean on: for the weighted completion time $\sum w_{k} C_{k}$ , an adjacent swap of $a$ (first) then $b$ changes cost by $w_{b} p_{a} - w_{a} p_{b}$ . This is non-negative exactly when $p_{a} / w_{a} \geq p_{b} / w_{b}$ , so the correct greedy sorts by the ratio $p_{k} / w_{k}$ (Smith's rule — weighted completion time), not by length alone. (Unweighted $\sum C_{k}$ is the special case $w_{k} = 1$ , recovering SPT.)

Compute the ratios $p / w$ . Job $a$ : $6/2 = 3$ . Job $b$ : $2/3 \approx 0.667$ . Smaller ratio first ⇒ $b$ before $a$ . Why this step? By the recapped rule, ordering $a$ before $b$ is bad exactly when $p_{a} / w_{a} \geq p_{b} / w_{b}$ , which holds here ( $3 \geq 0.667$ ).
Cost with $a$ first. $C_{a} = 6$ , $C_{b} = 6 + 2 = 8$ . Cost $= w_{a} C_{a} + w_{b} C_{b} = 2 \cdot 6 + 3 \cdot 8 = 12 + 24 = 36$ . Why this step? Direct evaluation of the objective for the "wrong" order (the inversion, since $a$ 's ratio $\geq$ $b$ 's).
Cost with $b$ first. $C_{b} = 2$ , $C_{a} = 2 + 6 = 8$ . Cost $= w_{b} C_{b} + w_{a} C_{a} = 3 \cdot 2 + 2 \cdot 8 = 6 + 16 = 22$ . Why this step? The order Smith's rule recommends.
Swap formula check. Here $O$ = ( $a$ first), $O^{'}$ = ( $b$ first). The general adjacent-swap change is $cost (O) - cost (O^{'}) = w_{b} p_{a} - w_{a} p_{b} = 3 \cdot 6 - 2 \cdot 2 = 18 - 4 = 14$ . Why this step? This general expression must equal $36 - 22$ .

Verify: $Δ = 36 - 22 = 14 = w_{b} p_{a} - w_{a} p_{b}$ . ✅ Ratio comparison: $3 > 0.667$ , so $a$ -first is worse, confirmed by $Δ > 0$ . Cell C — the sign of $Δ$ is governed by a ratio, not raw length.

Example 4 — Two-swap construction (cell D)

Worked example Huffman sibling lemma with real frequencies

Statement. Symbol frequencies $f (x) = 1$ , $f (y) = 2$ (the two smallest). In some optimal tree the deepest sibling leaves are $a, b$ with $f (a) = 4$ , $f (b) = 5$ , at depths $d_{a} = d_{b} = 3$ , while $x, y$ sit at depths $d_{x} = 1$ , $d_{y} = 2$ . Show the double swap does not increase cost.

Recap: a prefix code's cost is $\sum_{c} f (c) depth (c)$ (each symbol pays its frequency times how many bits its codeword uses). Swapping two leaves' positions moves each frequency to the other's depth; the cost change of one swap $u \leftrightarrow v$ collapses algebraically to $(f (v) - f (u)) (d_{u} - d_{v})$ .

Sign note. Here it is cleanest to track $Δ = cost (O^{'}) - cost (O)$ (new minus old — the reverse of the rest of the page), because the classic lemma wants to show $Δ \leq 0$ . We flag this so the direction never surprises you.

Forecast: two separate swaps happen. Guess — is the sum of both cost changes $\leq 0$ ?

First swap $x \leftrightarrow a$ . Change $= (f (a) - f (x)) (d_{x} - d_{a}) = (4 - 1) (1 - 3) = 3 \cdot (- 2) = - 6$ . Why this step? Apply the recapped one-swap identity with $u = x, v = a$ .
Second swap $y \leftrightarrow b$ . Change $= (f (b) - f (y)) (d_{y} - d_{b}) = (5 - 2) (2 - 3) = 3 \cdot (- 1) = - 3$ . Why this step? The construction of Huffman Coding's sibling lemma performs two swaps; you must account for both, not just one.
Total. $Δ = - 6 + (- 3) = - 9 \leq 0$ . Why this step? Each factor pattern is (non-neg frequency gap) $\times$ (non-pos depth gap, since $a, b$ are deepest) $\leq 0$ ; summing keeps it $\leq 0$ .

Verify: $Δ = - 9 < 0$ . ✅ Cost strictly drops here, so pushing $x, y$ to the deepest sibling slot never hurts — the sibling lemma holds. Had we counted only step 1 ( $- 6$ ) we'd have understated the improvement.

Example 5 — Degenerate input: ties (cell E)

Worked example Equal processing times,

$Δ = 0$ Statement. Two jobs, both length $p_{a} = p_{b} = 5$ , start at $t = 0$ , unweighted $\sum C_{k}$ . Does the order matter?

Forecast: with equal lengths, guess the cost difference.

Order $a$ then $b$ . $C_{a} = 5$ , $C_{b} = 10$ . Sum $= 15$ . Why this step? Standard completion-time evaluation.
Order $b$ then $a$ . $C_{b} = 5$ , $C_{a} = 10$ . Sum $= 15$ . Why this step? Symmetric to step 1.
Difference. $Δ = cost (O) - cost (O^{'}) = p_{a} - p_{b} = 5 - 5 = 0$ . Why this step? The strict-improvement identity ( $Δ = p_{a} - p_{b}$ , recapped at the top) becomes an equality when the keys tie.

Verify: $15 - 15 = 0 = p_{a} - p_{b}$ . ✅ Cell E — ties give $Δ = 0$ , so any tie-breaking order is optimal. This is why greedy proofs say "sort by key, break ties arbitrarily": the exchange argument still goes through with $\geq$ (never strict $>$ needed).

Example 6 — Zero / single element (cell F)

Worked example The base case that needs no swap

Statement. (a) An empty job list. (b) A single job of length $p_{1} = 9$ . Confirm greedy is trivially optimal and explain why the exchange induction bottoms out here.

Forecast: how many swaps are possible on a list of size $0$ or $1$ ?

Empty list. Total completion time $= \sum_{k} C_{k}$ over zero jobs $= 0$ . There is no pair to invert. Why this step? The exchange argument's Induction needs a base case; the empty schedule is vacuously optimal because there is only one solution.
Single job. Only order is $[9]$ , giving $C_{1} = 9$ , total $= 9$ . No index $j > i$ exists, so "find the twin later in $O$ " has nothing to swap. Why this step? The "first difference" index $i$ (first slot where $g_{i} \neq = o_{i}$ ) can only be found if two distinct orderings exist; with one element $G = O$ already.

Verify: empty cost $= 0$ ; single cost $= 9$ . ✅ Cell F — these are the induction base cases; every larger proof reduces down to them.

Example 7 — Where greedy FAILS (cell G)

Worked example No exchange lemma exists: coin change

${1, 3, 4}$ making 6 Statement. Denominations ${1, 3, 4}$ , make amount $6$ with fewest coins. Show greedy (take the largest coin $\leq$ remaining) is beaten, so no exchange lemma can hold.

Forecast: greedy grabs a $4$ first. Guess its coin count vs the true optimum.

Run greedy. $6 \to$ take $4$ (remainder $2$ ) $\to$ take $1$ (remainder $1$ ) $\to$ take $1$ (remainder $0$ ). Coins used: $4 + 1 + 1$ , count $= 3$ . Why this step? This is the local "largest first" rule — locally best is not always globally best.
Find the true optimum. $3 + 3 = 6$ , count $= 2$ . Why this step? We exhibit a better solution to prove greedy is not optimal.
Why no exchange proof exists. An exchange lemma would require: replacing an optimal coin with greedy's $4$ never increases the count. But swapping $3 + 3$ 's coins toward a $4$ forces two $1$ 's, raising the count $2 \to 3$ — the swap makes it worse ( $Δ = cost (O) - cost (O^{'}) = 2 - 3 = - 1 < 0$ ). Why this step? Cell G is the negative case: when $Δ < 0$ is possible, greedy is only a heuristic and you need Dynamic Programming.

Verify: greedy count $= 3$ , optimal count $= 2$ , and $3 > 2$ . ✅ Greedy strictly loses, so certifying it by exchange is impossible — contrast with matroid structures where Matroids and the greedy theorem guarantees an exchange property.

Example 8 — Real-world word problem (cell H)

Worked example Photocopier queue — minimise total wait

Statement. Four people queue at one photocopier with job times (minutes) $8, 2, 5, 3$ . Order them to minimise the sum of everyone's finish times (total waiting). What order, and what is the total?

Forecast: which person should go first? Guess the ordering, then the total.

Translate. "Sum of finish times" $= \sum C_{k}$ , unweighted — this is Ex 1's world. Greedy = Shortest Processing Time first (SPT). Why this step? Scheduling to minimise completion time maps a word problem to the SPT model, so cell H reduces to cell A.
Sort ascending. $2, 3, 5, 8$ . Any starting order with a longer job before a shorter one is an inversion; the cell-A argument removes each for a strict gain of $p_{long} - p_{short}$ , so the optimum is fully sorted. Why this step? The exchange argument (cell A) proved any inversion can be removed for a strict gain, so the optimum has no inversions — it is sorted.
Compute finish times of the sorted order. $C_{1} = 2$ ; $C_{2} = 2 + 3 = 5$ ; $C_{3} = 5 + 5 = 10$ ; $C_{4} = 10 + 8 = 18$ . Total $= 2 + 5 + 10 + 18 = 35$ . Why this step? Each finish time accumulates all earlier job lengths.
Compare a bad order (e.g. $8, 5, 3, 2$ ): $8, 13, 16, 18$ , total $= 55$ . Why this step? Confirms the sorted order is genuinely better, and the gap $55 - 35 = 20$ is the total of all inversion-removal gains.

Verify: SPT total $= 35$ ; the $8$ -first order gives $55$ , and $35 < 55$ . ✅ Units: minutes of cumulative waiting. Sorting saved $20$ person-minutes. Cell H closed — real words, cell-A machinery.

Example 9 — Exam twist: non-adjacent swap (cell I)

Worked example Bubble the far job forward — prove the full chain

Statement. Schedule $O = (a, x, b)$ with lengths $[p_{a}, p_{x}, p_{b}] = [9, 4, 2]$ starting at $t = 0$ , unweighted $\sum C_{k}$ . Greedy's first pick is the length- $2$ job $b$ (SPT), i.e. $g_{1} = b$ , but in $O$ it sits at position $3$ ( $o_{3} = b$ ) — non-adjacent to the front. Show the total drops when $b$ moves to the front, and that the total gain equals a sum of adjacent-swap gains — so a far swap is really a chain of "no worse" steps.

Forecast: moving $b$ two positions forward is two adjacent swaps. Guess whether the total gain equals the sum of each swap's gain.

Find the first difference. Greedy's first pick is $g_{1} = b$ , but $o_{1} = a \neq = b$ , so the first disagreeing slot is $i = 1$ . We must swap at this first difference (not an arbitrary one) so the induction marches toward $G$ . Why this step? Swapping at the first difference is what guarantees termination — after the swap, position $1$ matches greedy and stays matched.
Original order $O = (a, x, b)$ . $C_{a} = 9$ , $C_{x} = 9 + 4 = 13$ , $C_{b} = 13 + 2 = 15$ . Total $= 9 + 13 + 15 = 37$ . We can only justify adjacent swaps directly, so we bubble $b$ forward one neighbour at a time rather than teleporting it. Why this step? The adjacent-swap identity only applies to neighbours; a far move must be decomposed.
Swap $x \leftrightarrow b$ (first adjacent swap). New order $(a, b, x)$ . By the recapped identity, an adjacent swap of "longer $x$ before shorter $b$ " gains $Δ_{1} = p_{x} - p_{b} = 4 - 2 = 2$ . New total $= 37 - 2 = 35$ . Check: $C_{a} = 9, C_{b} = 9 + 2 = 11, C_{x} = 11 + 4 = 15$ , sum $= 35$ . ✅ Why this step? $b$ and $x$ are adjacent here, so the identity applies and the swap is "no worse" (here strictly better).
Swap $a \leftrightarrow b$ (second adjacent swap). New order $(b, a, x)$ . Adjacent swap of "longer $a$ before shorter $b$ " gains $Δ_{2} = p_{a} - p_{b} = 9 - 2 = 7$ . New total $= 35 - 7 = 28$ . Check: $C_{b} = 2, C_{a} = 2 + 9 = 11, C_{x} = 11 + 4 = 15$ , sum $= 28$ . ✅ Why this step? $b$ has now reached the front, so the schedule finally agrees with greedy's first pick — the induction proceeds on the tail $(a, x)$ .
Assemble the chain. We built $O = O_{0} = (a, x, b) \to O_{1} = (a, b, x) \to O_{2} = (b, a, x)$ (agrees with $G$ on pick 1), with $cost : 37 \geq 35 \geq 28$ . Total gain $cost (O_{0}) - cost (O_{2}) = 37 - 28 = 9$ and the two adjacent gains sum $Δ_{1} + Δ_{2} = 2 + 7 = 9$ . Why this step? This is the telescoping heart of the exchange argument: a non-adjacent move decomposes into a chain of adjacent swaps, each individually justified, so $cost (O) \geq cost (O_{1}) \geq \dots \geq cost (G)$ never rises.

Conclusion. Since every step was "no worse" (here strictly better) and we finished agreeing with greedy on the first job, the same reasoning applied recursively to the tail transforms $O$ fully into $G$ without ever increasing cost. Hence greedy (SPT) is optimal — cell I closed.

Verify: $37 - 28 = 9$ and the two adjacent gains sum $2 + 7 = 9$ . ✅ Cell I — a far swap is a chain of adjacent swaps, matching the telescoping inequality.

Recall

Recall Match the cell to the behaviour

Which cell has $Δ = 0$ (equal cost) because it counts objects? ::: Cell B (activity selection, maximisation). In cell C, what quantity decides who goes first? ::: The ratio $p_{k} / w_{k}$ (Smith's rule), not raw length. Why does cell G (coins ${1, 3, 4}$ , amount 6) admit no exchange proof? ::: A swap toward greedy's coin can increase the count ( $2 \to 3$ ), so "no worse after swap" is false ( $Δ < 0$ ). How does a non-adjacent swap (cell I) get justified? ::: As a chain of adjacent swaps, each with its own "no worse" inequality; gains sum. What does $g_{i}$ mean, versus $o_{i}$ ? ::: $g_{i}$ = greedy's $i$ -th choice in order; $o_{i}$ = the element in position $i$ of the optimal list $O$ .