Exchange Arguments: Proving Greedy Works

Quick Revisit

• USE WHEN: proving (or disproving) a greedy ordering — "sort by what criterion?"
• INVARIANT: swapping any two adjacent out-of-order elements never improves the solution
• TIME: O(n log n) for sort-based greedy | SPACE: O(n)
• CLASSIC BUG: wrong pairwise comparison — e.g., job scheduling needs wᵢ/tᵢ ratio, not wᵢ − tᵢ
• PRACTICE: 08-ladder-mixed

Greedy is the most dangerous technique in competitive programming. It looks right on small examples, it passes pretests, and then it fails on test 47 because your greedy ordering was subtly wrong. Exchange arguments are how you prove -- or disprove -- that a greedy strategy is correct.

Difficulty: [Advanced]CF Rating Range: 1700-2200 Prerequisites: Greedy

Contents

• The Exchange Argument Framework
• Proof 1: Activity Selection
• Proof 2: Minimizing Total Completion Time
• Proof 3: Huffman Coding
• Proof 4: Job Scheduling with Deadlines and Penalties
• When Exchange Arguments Fail
• The Proof Habit
• Practice Problems

---

The Exchange Argument Framework

Every exchange argument follows the same skeleton:

1. Assume an optimal solution OPT that differs from the greedy solution G.
2. Find two adjacent elements in OPT that violate the greedy ordering criterion.
3. Swap those two elements and show the resulting solution is no worse.
4. Repeat until OPT matches G (by induction / bubble sort argument).
5. Conclude G is optimal.

The heart of step 3 is always an inequality. You write down the cost before and after the swap and show ${\text{cost}}_{\text{after}}\le {\text{cost}}_{\text{before}}$.

Proof 1: Activity Selection

Problem: Given $n$ intervals $[s_i,f_i)$, select the maximum number of non-overlapping intervals.

Greedy: Sort by finish time $f_i$. Greedily pick the earliest-finishing interval that doesn't overlap the last selected one.

Exchange argument:

Let OPT be an optimal set that differs from greedy set G. Let $g_1$ be the first interval chosen by G, and $o_1$ the first interval in OPT. Since G picks the earliest finish time, $f_{g_1}\le f_{o_1}$.

Swap $o_1$ for $g_1$ in OPT. Since $g_1$ finishes no later than $o_1$, it can't create new overlaps with subsequent intervals in OPT. So the new set ${\text{OPT}}^{\prime }=\{g_1\}\cup (\text{OPT}\setminus \{o_1\})$ is still valid and has the same size.

Now OPT' agrees with G on the first choice. Repeat inductively for the remaining intervals. Eventually OPT is transformed into G without losing any intervals. $◻$

Proof 2: Minimizing Total Completion Time

Problem: $n$ jobs with processing times $p_1,\dots ,p_n$ on a single machine. Minimize $\sum C_j$ where $C_j$ is the completion time of job $j$.

Greedy (SPT rule): Schedule jobs in order of increasing processing time.

Exchange argument:

Suppose OPT has two adjacent jobs $i,j$ where $p_i>p_j$ but $i$ is scheduled before $j$. Let $T$ be the time at which job $i$ starts.

• Before swap: contribution of $i$ and $j$ is $(T+p_i)+(T+p_i+p_j)$.
• After swap: contribution is $(T+p_j)+(T+p_j+p_i)$.

Difference: $(2T+2p_i+p_j)-(2T+2p_j+p_i)=p_i-p_j>0$.

So the swap strictly decreases the total. This contradicts OPT being optimal unless no such pair exists -- i.e., OPT is already sorted by $p_i$. $◻$

Proof 3: Huffman Coding

Problem: Given character frequencies $f_1,\dots ,f_n$, build a binary tree minimizing $\sum f_i\cdot d_i$ where $d_i$ is the depth of character $i$.

Greedy: Repeatedly merge the two lowest-frequency nodes.

Exchange argument (sketch):

In any optimal tree, the two lowest-frequency characters must be siblings at the deepest level. Suppose not: say character $a$ (lowest frequency) is at depth $d_a$ and some character $b$ with $f_b>f_a$ is at a deeper or equal depth $d_b\ge d_a$.

Swap their positions. Cost changes by $f_a(d_b-d_a)-f_b(d_b-d_a)=(f_a-f_b)(d_b-d_a)\le 0$. So the swap doesn't increase cost.

After establishing the two lowest-frequency characters are siblings at the bottom, replace them with a single node of combined frequency and recurse. This is exactly what Huffman's algorithm does. $◻$

Proof 4: Job Scheduling with Deadlines and Penalties

Problem: $n$ unit-time jobs, each with a deadline $d_j$ and a penalty $w_j$ incurred if the job is late. Minimize total penalty.

Greedy: Sort jobs by penalty (largest first). Schedule each job at the latest available slot on or before its deadline. If no slot is available, the job is late.

Exchange argument:

Consider OPT where an on-time job $i$ with penalty $w_i$ is scheduled before an on-time job $j$ with $w_j>w_i$, and both finish before their deadlines. Swapping their time slots keeps both on time (if $j$ can still meet its deadline in $i$'s later slot). The total penalty doesn't change.

Now consider the case where a late job $j$ ($w_j$ large) could replace an on-time job $i$ ($w_i<w_j$) in $i$'s time slot. After swapping, $j$ is on time (saving $w_j$) and $i$ is late (costing $w_i$). Net savings: $w_j-w_i>0$. This contradicts OPT, so in any true optimal solution, no such swap is possible. $◻$

When exchange arguments fail

Failed exchange #1: a tempting swap that breaks feasibility

Problem. $n$ jobs, each with processing time $p_i$ and deadline $d_i$. Schedule them on one machine to minimize the number of late jobs (each job either makes its deadline or contributes 1 to the count).

Tempting greedy. "Sort by deadline ascending; ties broken by processing time descending." A reasonable instinct: do the jobs with tight deadlines first.

Attempted exchange argument. Take two adjacent jobs $i$, $j$ with $i$ before $j$ where $d_i>d_j$ (deadline order is wrong). Swap them, the argument goes — moving the tighter deadline earlier can only help.

Where it fails. Consider $i=(p=5,d=10)$ and $j=(p=1,d=6)$. In the order $i,j$: both finish on time (5, 6). After the swap to $j,i$: $j$ finishes at 1, $i$ finishes at 6 — but $i$'s deadline is 10, so still on time. Both orders are feasible. So far so good.

But add a third job $k=(p=4,d=8)$ at the end. With order $i,j,k$: finishes 5, 6, 10 → $k$ is late. With order $j,i,k$: finishes 1, 6, 10 → $k$ still late. Same total.

Try $i=(p=8,d=10)$, $j=(p=1,d=2)$. Order $i,j$: $i$ on time at 8, $j$ late (8+1=9 > 2). One late. Order $j,i$: $j$ on time at 1, $i$ on time at 9. Zero late. The swap helped.

Now try $i=(p=2,d=10)$, $j=(p=5,d=6)$. Order $i,j$: 2, 7 → $j$ late. Order $j,i$: 5, 7 → both on time. The swap helped because the finish times happened to fit. Take the same pair but with $j=(p=5,d=4)$: order $i,j$: 2, 7 → $j$ late. Order $j,i$: 5, 7 → both late ($j$ misses 4, $i$ misses 10). The swap did not preserve feasibility — neither order is feasible, but the swap doesn't strictly improve.

The lesson: the swap inequality "moving the tighter deadline earlier never worsens the count of late jobs" is not an identity. Whether it helps depends on the cumulative time before the pair, which is a global quantity. A correct algorithm here is Moore–Hodgson (sort by deadline, then drop the largest job from the prefix whenever capacity is exceeded) — and that algorithm's correctness needs more than a one-step adjacent swap.

Failed exchange #2: 0/1 knapsack

Problem. Items with (weight, value): $(1,6),(2,10),(3,12)$, capacity $W=5$.

Greedy by value/weight ratio picks item 1 ($6/1=6$), then item 2 ($10/2=5$). Total weight 3, value 16. But the optimal is items 2 and 3: weight 5, value 22.

The exchange fails because swapping isn't local — adding one item may force removing another due to the global capacity constraint. Exchange arguments need swaps that touch only the two elements involved.

Rule of thumb

If swapping two elements can change which other elements are feasible (global capacity, sequencing-dependent feasibility, packing constraints), the adjacent-swap argument breaks. The fix is usually DP on the resource or item subset.

The Proof Habit

In contests, you don't need to write a formal proof. But you should mentally:

1. Identify the greedy ordering -- what comparator sorts elements?
2. Imagine two adjacent out-of-order elements -- what happens when you swap?
3. Check the inequality -- does the swap never worsen the answer?

If you can't convince yourself in 30 seconds, the greedy is probably wrong. Switch to DP. This 30-second mental check saves hours of debugging wrong greedy solutions.

Practice Problems

Problem	Key Insight	CF Rating
CF 1203F1 - Complete the Projects (easy)	Sort by gain/loss, exchange argument on ordering	1800
CF 1491C - Pekora and Trampoline	Greedy simulation with exchange justification	1700
CF 1665C - Tree Infection	Binary search + greedy check, exchange on priority	1600
CF 1374E2 - Reading Books (hard)	Sort by contribution, exchange argument	1900
CF 580B - Kefa and Company	Sort + two pointers, greedy ordering proof	1500
CF 1443C - The Delivery Dilemma	Binary search the answer + greedy feasibility	1400

Related Techniques

• Greedy -- exchange arguments are the primary proof technique for greedy correctness
• Sorting and Searching -- most exchange arguments reduce to "sort by this comparator"
• DP vs Greedy Guide -- when exchange arguments fail, the problem likely needs DP instead

---