i. Greedy and Exchange Arguments

A greedy algorithm commits to the locally best choice and never undoes it. It’s correct when some optimal solution starts with the greedy choice and the rest is the same problem again. Unproven greedy is the most common source of WA, so the proof technique matters as much as the rule.

Finding the rule

1. Brute force small inputs and look at optimal solutions. What’s chosen first? In what order?
2. Try sort keys: value, deadline, end time, ratio $a/b$, difference $a-b$, sum $a+b$, or a comparator derived from two elements (below).
3. Stress test the candidate rule against a brute force before coding the real thing.

Adjacent exchange: finding the sort key

For “order items to minimise a cost”, look at two adjacent items. Put $i$ before $j$ iff $\text{cost}(\dots ij\dots )\le \text{cost}(\dots ji\dots )$, and rearrange it into $f(i)\le f(j)$.

Smith’s rule (minimise $\sum w_i{C}_i$ on one machine): $i$ first costs $w_i{p}_i+w_j(p_i+p_j)$, $j$ first costs $w_j{p}_j+w_i(p_i+p_j)$. So $i$ goes first iff $p_i/w_i\le p_j/w_j$.

Proof: Smith's rule, and why adjacent exchange proves a global order

Local step. $i$ before $j$ costs $w_i{p}_i+w_j(p_i+p_j)$ and $j$ before $i$ costs $w_j{p}_j+w_i(p_i+p_j)$; every other job’s completion time is unaffected by swapping only $i,j$ (they occupy the same two time slots either way, and no job outside the pair moves). Subtracting, ($i$-first cost) $-$ ($j$-first cost) $=(w_i{p}_i+w_j{p}_i+w_j{p}_j)-(w_j{p}_j+w_i{p}_i+w_i{p}_j)=w_j{p}_i-w_i{p}_j$. So $i$-first is at most as costly as $j$-first iff $w_j{p}_i\le w_i{p}_j$, i.e. (dividing by $w_i{w}_j>0$) iff $p_i/w_i\le p_j/w_j$. Global step. If some optimal order has $i$ immediately after $j$ with $p_i/w_i\le p_j/w_j$, swapping them keeps the same set of jobs and the same completion times for everyone else, and by the local step does not increase cost — so some optimal order has no adjacent inversion against this key, i.e. is sorted by $p/w$. Since any order can be turned into the fully sorted one through a sequence of adjacent swaps that each fix one inversion, and each such swap is non-worsening by the local step, the sorted order is itself optimal. $■$

More keys derived the same way:

Objective	Sort by
$\min \sum C_j$	shortest processing time first
$\min \max L_j$ (lateness)	earliest deadline
$\min \sum w_j{C}_j$	$p_j/w_j$ ascending (compare as $p_i{w}_j<p_j{w}_i$)
boxes/people stacking with strength $s$ and weight $w$, minimise max load	$s+w$
concatenate numbers into the largest number	$a+b>b+a$ as strings
tasks with requirement $r_i$ to start and cost $c_i$: complete as many as possible	$r_i-c_i$ descending
dragons/monsters where defeating $i$ needs strength $s_i$ and gives $g_i$	$g\ge 0$ first by $s$ ascending; then $g<0$ by $s+g$ descending
two-machine flow shop	Johnson’s rule (Scheduling)

Transitivity

The pairwise rule must be a strict weak ordering. Ratios, differences and sums are fine. For an unusual rule, test transitivity on random triples, or prove it by writing the comparison as $f(i)<f(j)$. When ties matter (equal keys with different effects), add a second key and re-prove.

Exchange for selections

Take an optimal solution $O$ and the greedy solution $G$. At the first difference, swap in greedy’s choice; show feasibility is kept and the objective doesn’t get worse. By induction, some optimal solution equals $G$.

A second proof style, potential / bound, needs no exchange: find an a priori lower bound on the objective (an invariant, a counting argument, a matroid rank), then show greedy’s output meets it exactly. This is often shorter when the bound is easy to state (e.g. $\ge$ the number of components merged, $\ge$ a sum over a fixed set of constraints) but the exchange step would be fiddly.

Greedy stays ahead is the same idea measured stepwise: after $k$ steps, greedy’s progress is at least as good as any solution’s after $k$ steps. Interval scheduling by earliest finish: the $k$-th greedy interval ends no later than the $k$-th of any feasible schedule.

Proof: earliest-finish-first is optimal for interval scheduling

Let $G=g_1,g_2,\dots$ be greedy’s choices and $O=o_1,o_2,\dots$ any feasible (pairwise non-overlapping) set of intervals, both sorted by finish time. Claim: $\mathrm{finish}(g_k)\le \mathrm{finish}(o_k)$ for every $k$ for which both exist. By induction on $k$: for $k=1$, $g_1$ is the earliest-finishing interval overall, so $\mathrm{finish}(g_1)\le \mathrm{finish}(o_1)$. For the step, assume $\mathrm{finish}(g_{k-1})\le \mathrm{finish}(o_{k-1})$; since $o_k$ starts after $o_{k-1}$ finishes, $o_k$ starts after $g_{k-1}$ finishes too, so $o_k$ is a candidate greedy could have picked at step $k$ (compatible with $g_1,\dots ,g_{k-1}$); greedy picks the earliest-finishing such candidate, so $\mathrm{finish}(g_k)\le \mathrm{finish}(o_k)$. This proves the claim. Now suppose $|O|>|G|$: then $o_{|G|+1}$ exists and starts after $\mathrm{finish}(o_{|G|})\ge \mathrm{finish}(g_{|G|})$ (by the claim at $k=|G|$), so $o_{|G|+1}$ is compatible with all of $G$ — but then greedy would not have stopped at $|G|$ intervals, a contradiction. So $|O|\le |G|$ for every feasible $O$, i.e. $G$ is optimal. $■$

Regret greedy (priority queue with undo)

Take tentatively. When the constraint breaks, throw away the worst item taken so far. The proof is an exchange: the discarded item is never better than what replaced it.

Proof: regret greedy for unit jobs with deadlines maximises profit

Process jobs in deadline order, maintaining a set $S$ of currently-accepted jobs with $|S|\le d$ for every prefix processed so far (enforced by discarding the minimum-profit job in $S$ whenever a new job would push some deadline’s count too high). Claim: at every point, $S$ has the maximum possible total profit among sets of size $|S|$ that are feasible using only the jobs seen so far. By induction on the number of jobs processed: adding a new job $j$ with profit $p$ either fits (feasible sets of the new size containing $j$ plus an optimal old $S$ are optimal, since $j$ is forced available at this point and nothing before benefits from excluding it) or forces a removal; when forced, removing $\min (S\cup \{j\})$ is correct because any feasible set of the same size using the same job pool has to drop some job to stay within every deadline’s capacity, and dropping the globally smallest profit among all currently-held candidates (old $S$ plus $j$) cannot be beaten by dropping any other single job — any other choice of removal leaves a set with total profit at most the profit of keeping the $|S|$ largest values, which is exactly what discarding the minimum achieves. Formally: among all subsets of $S\cup \{j\}$ of size $|S|$, the one maximising profit sum is the one dropping the single smallest element, since removing any other element $e\ne \min$ instead of $\min$ gives a set containing $\min$ but missing $e$, with profit sum smaller by $p_e-p_{\min }\ge 0$. Since the deadline constraint only bounds $|S|$ (unit jobs, one slot per time unit up to each deadline), any set respecting all capacity bounds is exactly a set of the right size at every prefix, so maximising the sum at every step maximises it at the end. $■$

// unit jobs with deadlines d and profits p: maximise total profit
sort(all(jobs));                                   // by deadline
priority_queue<ll, vector<ll>, greater<>> taken;   // min-heap of profits
for (auto [d, p] : jobs) {
    taken.push(p);
    if ((int)taken.size() > d) taken.pop();        // too many jobs before deadline d
}

The same shape covers:

• Moore-Hodgson (fewest late jobs): drop the longest job taken so far when the deadline is violated.
• Minimum refuelling stops: when out of fuel, refuel at the best station passed.
• Buy low, sell high with unlimited transactions and one share per day (CF 865D): push each price twice. When the current price beats the cheapest in the heap, take the profit and push the current price so the trade can later be “extended”.
• Choosing $k$ non-adjacent elements with maximum sum: take the maximum $a_i$, replace it and its neighbours by $a_{i-1}+a_{i+1}-a_i$ (a regret node), repeat $k$ times with a heap and a linked list. This is a simple instance of the general “simulate min-cost flow augmentations with heaps” technique.

Greedy as simulated flow

Many greedy-with-heap solutions are min-cost flow where every augmenting path is short (one or two edges) and can be found with heaps. If a problem is naturally a flow (matching people to items on a line, buy and sell, assigning tasks with capacities) and $n$ is $10^5$-$10^6$, look for the greedy that simulates the augmentations, with “regret” entries representing reverse edges.

Huffman coding and optimal merging

Repeatedly merge the two smallest weights. The cost (sum of weights times depth, or the total merge cost of sorted runs) is minimised.

Proof: Huffman merging minimises $\sum w_i\cdot {\mathrm{depth}}_i$

Two smallest weights are deepest siblings in some optimal tree. In any full binary tree (every internal node has 2 children — an optimal tree is always full, else a unary node could be removed, strictly improving cost), two of the deepest leaves are siblings. Let $a,b$ have the two globally smallest weights. If the sibling pair at maximum depth is $\{x,y\}\ne \{a,b\}$, swap $a$ into $x$‘s position and $x$ into $a$‘s (and likewise for $b,y$ if needed): since $w_a\le w_x$ and $\mathrm{depth}(x)\ge \mathrm{depth}(a)$ (as $x$ was at the deepest level), moving the smaller weight to the deeper position changes the cost by $(w_a-w_x)(\mathrm{depth}(x)-\mathrm{depth}(a))\le 0$ — cost does not increase. Repeating for the second element produces an optimal tree with $a,b$ as deepest siblings. Reduction. In that tree, replace the pair $a,b$ by a single leaf $z$ with weight $w_a+w_b$ at their shared parent’s position: $\mathrm{cost}(T)=\mathrm{cost}(T^{\prime })+w_a+w_b$, where $T^{\prime }$ is the tree on the remaining $n-1$ symbols (every other leaf keeps its depth; $a,b$ each lose one level of depth relative to $z$, accounting for the $+w_a+w_b$ exactly, since $w_a\cdot \mathrm{depth}(a)+w_b\cdot \mathrm{depth}(b)=(w_a+w_b)(\mathrm{depth}(z)+1)=(w_a+w_b)\mathrm{depth}(z)+w_a+w_b$). So minimising $\mathrm{cost}(T)$ over trees with $a,b$ as siblings is equivalent to minimising $\mathrm{cost}(T^{\prime })$ over trees on the reduced problem, plus the constant $w_a+w_b$. Induction on $n$ (base case $n\le 2$: the only tree is optimal) gives that repeatedly merging the two smallest weights is optimal at every step, hence overall. Prefix-free. Every symbol sits at a distinct leaf and codes are root-to-leaf paths, so no code is a prefix of another (that would require one leaf to be a proper ancestor of another, impossible in a tree where every symbol is a leaf). $■$

• $O(n)$ after sorting: two queues, one of sorted leaves and one of merged nodes (merged sums come out in non-decreasing order).
• $k$-ary Huffman: pad with zero-weight leaves until $(n-1)\mathrm{mod}(k-1)=0$, then merge the $k$ smallest each time.
• If the order of leaves must be kept (alphabetic codes, optimal BST-like merging of adjacent piles), greedy fails: use Hu-Tucker or Garsia-Wachs, or the interval DP with Knuth’s optimisation (Knuth-Yao).
• Adaptive Huffman: update the tree as symbols stream in with no upfront frequency table (FGK/Vitter algorithms).
• Canonical Huffman: reassign codes by (length, symbol order) only, so the code table transmits as just a list of lengths.
• Arithmetic / range coding: a different entropy coder that beats Huffman on skewed distributions by not rounding each code to a whole number of bits; used alongside Huffman-style merging in JPEG, DEFLATE and MP3.
• The same two-smallest-first merge minimises total cost for merging sorted runs in external sorting (optimal merge patterns) — it’s the same proof, with “merge cost” standing in for “weighted depth”.

Classic greedy table

Problem	Rule
max non-overlapping intervals	earliest end
min points stabbing all intervals	sort by end, place a point at each uncovered end
min rooms	max overlap depth; assign with a min-heap of end times
fractional knapsack	value / weight descending
assign tasks to workers, maximise matches with $a_i\le b_j$	sort both, two pointers
minimise $\sum |a_i-b_{\pi (i)}|$	sort both, pair in order
maximise $\sum a_i{b}_{\pi (i)}$	sort both the same way (rearrangement inequality)
jump game, min jumps	BFS-like ranges: furthest reach per layer
canonical coin systems	largest coin first (check canonicity by brute force up to the sum of the two largest coins)
MST	Kruskal / Prim (cut property)
matroid maximum weight basis	sorted greedy (Matroids)

Recognising a matroid is itself a correctness proof — no exchange argument needed, since greedy-by-weight is always optimal on a matroid’s independent sets (Matroids). Common matroids worth spotting on sight: spanning forests (graphic matroid, $\to$ Kruskal), linearly independent vectors over a field or ${\mathbb{F}}_2$ ($\to$ linear/XOR basis), partition matroids (at most $k_i$ items from group $i$), uniform matroids (any $k$ items), and scheduling unit jobs against deadlines (a transversal matroid — this is exactly why the regret-greedy construction above works).

Proof: sorting both arrays the same way minimises $\sum |a_i-b_{\pi (i)}|$

Lemma. For any reals $a\le b$ and $c\le d$: $|a-c|+|b-d|\le |a-d|+|b-c|$. Using the representation $|u-v|={\int }_{-\infty }^{\infty }|1[t<u]-1[t<v]|dt$, fix any $t$ and write $I_a=1[t<a]$, etc.; since $a\le b$ and $c\le d$, $I_a\le I_b$ and $I_c\le I_d$ as 0/1 values. Checking the (small number of) possible combinations of $(I_a,I_b)\in \{(0,0),(0,1),(1,1)\}$ and $(I_c,I_d)\in \{(0,0),(0,1),(1,1)\}$ directly: whenever $I_a=I_b$ or $I_c=I_d$, both sides of the pointwise inequality $|I_a-I_c|+|I_b-I_d|\le |I_a-I_d|+|I_b-I_c|$ are equal; the one remaining combination $I_a=0,I_b=1,I_c=0,I_d=1$ gives left side $0+0=0$ and right side $1+1=2$, so $0\le 2$ holds. The pointwise inequality holds in every case, so it holds after integrating over $t$, proving the lemma.
Applying it. Suppose $a$ (equivalently the sequence paired with $a$, here renamed to match the lemma) is sorted and $\pi$ is not order-preserving on $b$: then there exist $i<j$ with $a_i\le a_j$ but $b_{\pi (i)}>b_{\pi (j)}$. Set $x=a_i\le a_j=y$ and $c=b_{\pi (j)}\le b_{\pi (i)}=d$ (renaming so $c\le d$ matches the lemma). The current pairing contributes $|x-d|+|y-c|$ (the cross pairing); swapping to match $x$ with $c$ and $y$ with $d$ contributes $|x-c|+|y-d|$ instead, with every other term unchanged. The lemma (with $a=x,b=y,c,d$ as just defined) says exactly $|x-c|+|y-d|\le |x-d|+|y-c|$, so the swap never increases the total cost. Repeating removes every inversion between $\pi$‘s induced order on $b$ and the sort order on $a$, reaching the fully sorted pairing without ever increasing the cost — so some optimal pairing is the sorted one. $■$

When greedy fails

Problem	Why
0/1 knapsack	indivisible items; ratio order isn’t optimal
coin change with $\{1,3,4\}$, target 6	largest-first gives 3 coins, optimum is 2
weighted interval scheduling	one long valuable interval vs several short ones; DP
set cover, vertex cover, TSP	NP-hard; greedy gives only approximations ($\ln n$, 2, $\log n$)
graph coloring	depends on vertex order (optimal on interval/chordal graphs with the right order)

An exchange argument that doesn’t close is evidence the greedy is wrong. Look for the counterexample with 3-4 elements.

Practice

CSES: Movie Festival, Tasks and Deadlines, Stick Lengths, Room Allocation, Factory Machines (binary search + greedy). Codeforces: the “greedy” tag, rating 1200–2000, is the densest source of exchange-argument practice.