1
Greed is a design pattern, not a guarantee
It produces an answer quickly. Whether that answer is optimal is a separate theorem about the specific problem.
Lesson · Algorithms and Complexity · Design
Greedy Algorithms
A greedy algorithm never reconsiders. Sometimes that is provably optimal — minimum spanning trees, interval scheduling, Huffman codes — and usually it is not, so the proof is the whole content.
greedy: make the locally best choice, never revisit
correct when a GREEDY CHOICE PROPERTY holds
exchange argument: any optimum can be modified toward the greedy choice
coins {1,3,4}: greedy fails at 6 (4+1+1 vs 3+3)
Fast, and usually wrong
Core ideas
What this lesson establishes
Greedy algorithms are easy to write and hard to justify, and the justification is what separates a method from a heuristic.
2
The exchange argument is the standard proof
Take any optimal solution and show it can be modified to agree with the greedy choice without getting worse.
3
Failure is common and often silent
Coin change with {1,3,4} fails at 6. Nothing in the algorithm signals it, which is why the proof matters.
The material
Greedy algorithms
Three where it works, one where it fails, and the proof technique.
Interval scheduling
Given intervals with start and finish times, select as many non-overlapping ones as possible. The greedy rule is: repeatedly take the interval that finishes earliest among those compatible with what is already chosen.
Theorem · Earliest finish time is optimal
The greedy algorithm selects a maximum-size set of pairwise compatible intervals.
Let g₁, g₂, … be the greedy selection in order and o₁, o₂, … an optimal one, both sorted by finish time. We show by induction that gᵢ finishes no later than oᵢ.
For i = 1, greedy chose the earliest-finishing interval overall. For the step, if gᵢ finishes no later than oᵢ, then o_{i+1} is available to greedy at step i+1, so g_{i+1} finishes no later.
If the optimum had more intervals than greedy, its next interval would be compatible with everything greedy chose, so greedy would not have stopped. Hence the sizes are equal.
□
Other plausible rules fail. Shortest interval first fails on a short interval overlapping two long disjoint ones. Earliest start first fails on one very long interval that begins first. Only earliest finish is optimal, and the difference is not visible without the proof.
Where greedy fails
Example · Coin change
With {1, 5, 10, 25} the greedy rule — largest coin first — is optimal for every amount. With {1, 3, 4} it fails at 6: greedy gives 4 + 1 + 1 (three coins) while 3 + 3 uses two. "Greedy works for coin change" is a property of the coin system, not of the strategy.
Example · The travelling salesman
Nearest-neighbour tour construction can be arbitrarily bad: instances exist where it exceeds the optimum by any factor you like. Greedy gives a tour quickly and offers no guarantee at all.
The exchange argument
The standard proof technique has three steps. Assume an optimal solution differing from the greedy one. Find the first place they differ. Show the optimum can be modified to agree with greedy there without becoming worse. Repeating turns the optimum into the greedy solution, so greedy is optimal too.
This is exactly the argument used for the cut property in “Spanning Trees and Minimum Spanning Trees” in Graphs and Trees: swapping the heavier edge for the lighter one in a minimum spanning tree does not increase the total. The technique is the same wherever greedy is correct.
Huffman coding
Theorem · Huffman codes are optimal
Repeatedly merging the two least frequent symbols into a combined node produces a prefix-free binary code of minimum expected length.
The greedy choice is merging the two rarest symbols, and the exchange argument shows an optimal tree can always be modified to place them as siblings at the deepest level. It is the compression method behind several standard formats, and its optimality is a genuine theorem rather than an observation.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Designing a greedy algorithm
Write it, then prove it, then test it.
1
Identify the greedy choice
The locally best option: earliest finish, lightest edge, largest coin, rarest symbol.
2
Attempt an exchange argument
Can any optimal solution be modified to include the greedy choice without getting worse? If yes, greedy is optimal.
3
If the proof fails, look for a counterexample
Small instances usually reveal it. Coin change fails at 6 with a three-coin system.
4
Say what you have
"Optimal, by exchange argument" or "a heuristic with no guarantee". Both are legitimate; conflating them is not.
Greedy
Score 0 / 0Choose the answer you can justify.
Two greedy rules for interval scheduling
Intervals A(0,10), B(1,3), C(4,6), D(7,9).
EARLIEST START FIRST
A (0,10) chosen first — it blocks everything else
result: {A}, 1 interval
SHORTEST FIRST
B (1,3) length 2, C (4,6) length 2, D (7,9) length 2, A length 10
result: {B, C, D}, 3 intervals — optimal here, by luck
EARLIEST FINISH FIRST
B finishes at 3, then C at 6, then D at 9
result: {B, C, D}, 3 intervals — optimal, PROVABLY
Shortest-first fails elsewhere: intervals (0,5), (4,6), (5,10)
shortest first takes (4,6) and blocks both others → 1
earliest finish takes (0,5) then (5,10) → 2
Three rules, all plausible, and only one is optimal in general. The second happened to work on the first instance and fails on the second, which is exactly why a counterexample search is not a substitute for a proof.
Common mistakes
1
Assuming greedy is optimal because it seems reasonableThree plausible rules for interval scheduling, one correct. The proof is the only way to tell.
2
Testing instead of provingShortest-first passes the first example and fails the second. The point of “Cases, Counterexamples, and Writing a Proof”, in Logic and Proof, applies unchanged.
3
Not saying which you have"Optimal by exchange argument" and "a heuristic" are both respectable. Presenting the second as the first is not.
Check your understanding
✓
Finish when you attempt the exchange argument before trusting a greedy rule.
For the fractional knapsack problem — items may be split — show that taking items in decreasing value-per-weight order is optimal. Then observe that the 0/1 version, where items cannot be split, defeats the same rule, and “Dynamic Programming” handles it.
Note: The structure making greed provably correct is a matroid, and the forests of a graph form one — which is why Kruskal's algorithm works. Most problems have no such structure, and dynamic programming is the usual alternative.