Greedy Algorithms
A greedy algorithm builds a solution one piece at a time, always choosing the option that looks best right now without revisiting earlier decisions. When greedy works, the resulting code is short and fast. The catch: it does not always work — proving correctness is the hard part.
Activity Selection
Given a list of activities with start and end times, the goal is to pick the largest set you can attend without overlap. The greedy rule: sort by end time, then pick each activity that starts at or after the end of the last one you picked.
Why does this work? After picking the activity that finishes earliest, you have the most time left for everything else. Any other first choice leaves less room. Inducting on this argument shows greedy is optimal here.
Coin Change
To make change for an amount using the fewest coins, the greedy approach is: take the largest coin that fits, subtract, repeat. With US-style denominations (1, 5, 10, 25, 100) this is provably optimal. With arbitrary denominations it is not — for coins of {1, 3, 4} and amount 6, greedy gives 4 + 1 + 1 = 3 coins, but the optimal answer is 3 + 3 = 2.
This is the recurring lesson with greedy: the algorithm is only as good as the proof behind the greedy choice.
When Greedy Works
A problem has a greedy solution if it has two properties:
- Greedy choice property — a globally optimal solution can be reached by making a locally optimal choice
- Optimal substructure — the optimal answer is built from optimal answers to subproblems
If only the second holds, you usually need dynamic programming instead.
Classic Greedy Problems
You will see greedy show up across the field:
- Huffman coding — assign shorter codes to more frequent symbols
- Minimum spanning tree (Kruskal's, Prim's) — build a tree by repeatedly adding the cheapest safe edge
- Job scheduling with deadlines — sort by profit, schedule each job into the latest free slot before its deadline
- Fractional knapsack — sort by value-per-unit-weight, take greedily
Try It Yourself
- Show why greedy fails for coins
{1, 3, 4}and amount 6, then write a DP solution that works - Modify activity selection to print which activities were skipped and why
- Implement Kruskal's algorithm: sort edges by weight, add each that does not form a cycle