Take the locally best option, never look back, and sometimes end up with the globally best answer — but only when the problem has a property you must prove.
A greedy algorithm makes the choice that looks best right now and commits to it, never reconsidering. That is dramatically cheaper than dynamic programming, which considers every choice and takes the best after the fact. The catch is that greedy is usually wrong. This chapter is really about the one property — the greedy-choice property — that separates the problems where greed works from the many where it does not, and how to prove you are in the first category.
n activities compete for one resource. Activity i has start time sᵢ and finish time fᵢ. Two activities are compatible if their intervals do not overlap. Select a maximum-size set of mutually compatible activities.
f₁ ≤ f₂ ≤ … ≤ fₙ.GREEDY-ACTIVITY-SELECTOR(s, f, n)
1 A = {a₁} // first to finish is always in
2 k = 1
3 for m = 2 to n
4 if s[m] ≥ f[k] // starts after the last selected finishes
5 A = A ∪ {aₘ}
6 k = m
7 return AΘ(n) after sorting, so Θ(n lg n) overall — a single pass. Compare with a DP formulation of the same problem, which is Θ(n³).
The standard proof shape, used for every greedy algorithm in the book:
Theorem 15.1 for activity selection. Let Sₖ be a subproblem and aₘ the activity in it with earliest finish time. Then aₘ is in some maximum-size subset of compatible activities of Sₖ.
Proof. Let Aₖ be a maximum-size compatible subset, and let aⱼ be its earliest-finishing member. If aⱼ = aₘ, done. Otherwise consider Aₖ′ = Aₖ - {aⱼ} ∪ {aₘ}. Since fₘ ≤ fⱼ and everything else in Aₖ starts after fⱼ, everything still fits. Aₖ′ has the same size and is compatible, so it is also optimal — and it contains aₘ. □
Note what this buys: after making the greedy choice, only one subproblem remains. There is no need to try alternatives, so no table, no memoisation, and the algorithm is a single loop.
Two properties are required, and the first is the one that distinguishes greedy from DP.
The chapter’s design procedure:
1. Cast the problem as one where you make a choice and are
left with ONE subproblem.
2. Prove there is always an optimal solution making the greedy
choice, so the choice is always safe.
3. Show that combining the greedy choice with an optimal solution
to the remaining subproblem gives an optimal solution overall.Both need optimal substructure, so the substructure alone does not tell you which to use. The classic pair of problems makes the difference sharp.
| Fractional knapsack | 0-1 knapsack | |
|---|---|---|
| Rules | You may take any fraction of an item | Each item is taken whole or not at all |
| Method | Greedy: sort by value per pound, take the best until full | Dynamic programming over capacity |
| Cost | Θ(n lg n) | Θ(nW) |
| Why | The last item can be split to fill the knapsack exactly, so no capacity is ever wasted | Leftover capacity may be wasted, and whether that is acceptable depends on later items — the greedy-choice property fails |
A compression problem. Given characters with frequencies, assign each a binary codeword to minimise the total encoded length. Codes must be prefix-free — no codeword is a prefix of another — so decoding is unambiguous and needs no separators.
T is B(T) = ∑ c.freq · dᴛ(c), the frequency-weighted sum of depths. An optimal code corresponds to a full binary tree, one where every internal node has two children.HUFFMAN(C)
1 n = |C|
2 Q = C // min-priority queue keyed on freq
3 for i = 1 to n - 1
4 allocate a new node z
5 z.left = x = EXTRACT-MIN(Q) // two rarest
6 z.right = y = EXTRACT-MIN(Q)
7 z.freq = x.freq + y.freq
8 INSERT(Q, z)
9 return EXTRACT-MIN(Q) // the rootThe greedy choice: merge the two lowest-frequency characters. With a binary min-heap from Chapter 6, this is O(n lg n) — n-1 iterations, each doing three O(lg n) heap operations.
Why the greedy choice is safe (Lemma 15.2). Let x and y be the two lowest-frequency characters. There exists an optimal prefix code in which they are siblings at maximum depth. The exchange argument: take an optimal tree, find the two deepest siblings, and swap them with x and y. Since x and y have the lowest frequencies, moving them deeper and the others shallower cannot increase the weighted cost.
Lemma 15.3 supplies the optimal substructure: replacing x and y by a merged character of combined frequency yields a smaller problem whose optimal solution extends to an optimal solution of the original. Together the two lemmas give Theorem 15.4: HUFFMAN produces an optimal prefix code.
New in the 4th edition, and it makes a nice bookend with Chapter 27.
A cache holds k blocks. A sequence of n block requests arrives. On a cache miss the block must be fetched, and if the cache is full something must be evicted. Minimise the number of misses. In the offline version you know the entire request sequence in advance.
Θ(n lg n). Shortest-first, fewest-conflicts, and earliest-start all fail.O(n lg n), provably optimal, and the tree is the prefix-free code.Chapter 16 introduces amortized analysis, a different kind of tool: not a way to design algorithms but a way to account for them, showing that an occasional expensive operation is paid for by many cheap ones. It finally proves the dynamic-array doubling claim from Chapter 10, and its techniques are needed for the disjoint-set forests of Chapter 19.