Greedy Algorithms: When the Local Best Wins
When a greedy algorithm is correct: earliest-finish activity selection is optimal, but greedy coin change fails for coins 1, 3, 4 at amount 6, using 3 coins where 2 will do.
A greedy algorithm builds an answer by taking the best-looking choice at each step and never revisiting it. It is correct only when the problem has the greedy-choice property and optimal substructure, usually shown by an exchange argument. Interviewers expect a counterexample: greedy coin change with coins 1, 3, 4 uses three coins for 6 where two suffice.
A greedy algorithm repeatedly takes the best-looking choice and never revisits it. That is right only when the problem has the greedy-choice property. Earliest-finish activity selection is provably optimal, but greedy coin change works for coins 25, 10, 5, 1 and fails for 1, 3, 4: it uses 3 coins for 6 where 2 is possible.
- A greedy algorithm is correct when the problem has the greedy-choice property, meaning some optimal solution contains the greedy first choice, and optimal substructure.
- Activity selection is solved optimally by sorting intervals by earliest finish time and taking each one that starts no earlier than the last chosen one ends.
- Greedy coin change gives the optimal 6 coins for amount 63 with coins 25, 10, 5, 1, but for coins 1, 3, 4 and amount 6 it uses 3 coins where 2 are enough.
- Checking every amount from 1 to 49 with coins 1, 3, 4, greedy coin change was wrong at 6, 10, 14, 18, 22, 26, 30, 34, 38, 42 and 46.
- Dijkstra's shortest path, Kruskal's and Prim's minimum spanning tree, Huffman coding and fractional knapsack are greedy algorithms; 0/1 knapsack needs dynamic programming.
- Over 2,000 random sets of 10 intervals checked by brute force, earliest-finish greedy was always optimal, while earliest start lost on 887, shortest first on 110 and fewest overlaps on 26.
01What greedy means
A greedy algorithm builds an answer in steps. At each step it takes the choice that looks best right now, without looking ahead and without undoing it later. This makes greedy algorithms simple and fast, often just a sort followed by a single pass: O(n log n) for the sort, O(n) for the pass.
The catch is correctness: a locally best choice can lead to a worse total. So the real skill is knowing when greedy is provably right, and having a test to catch when it is not.
Every greedy solution has three parts: a rule that ranks the candidates, a check that the next one still fits, and a commitment that is never reversed. The ranking rule is the whole algorithm.
02Works: activity selection
def select(intervals):
chosen, end = [], -1
for s, e in sorted(intervals, key=lambda x: x[1]): # by finish time
if s >= end: # fits after last
chosen.append((s, e))
end = e
return chosenTake one day of bookings for a shared lab machine, in hours on a 24-hour clock: (8,12) (10,11) (11,13) (11,15) (13,16) (14,16) (15,16) (17,18) (17,19). The function returns (10,11) (11,13) (13,16) (17,18), four bookings, which brute force confirms is the maximum. Sorting by earliest finish leaves the most room for later ones. Sorting by earliest start would be wrong: (8,12) starts first, but it blocks the three bookings starting at 10 or 11 and leaves room for only 3 in total.
The diagram traces the run. Rows are in the order the loop sees them. (10,11) is taken first, so (8,12) is skipped for starting before 11. (11,13) fits and moves the boundary to 13, which rules out (11,15). (13,16) wins the tie at 16 by coming first in the list. Finally (17,18) beats (17,19).
Here s >= end lets touching bookings share a boundary, so (11,13) may follow one ending at 11. If a gap is required, the test becomes s > end.
03Proving a greedy choice is safe
Tests find bugs; a proof shows there are none. Two standard proofs cover most interview problems.
Exchange argument. Take any optimal solution O, swap the greedy first choice into it, and show the result is still valid and no worse. Then repeat on what is left. For intervals, let o1 be the earliest-finishing activity in O. Greedy took g1, the earliest finisher of all, so g1 ends no later than o1. Every other activity in O starts no earlier than o1 ends, hence no earlier than g1 ends, so replacing o1 with g1 keeps the schedule legal and the same size.
Greedy stays ahead. Put greedy's picks g1, g2, ... and an optimal schedule o1, o2, ... in finish order. By induction, the i-th greedy pick finishes no later than the i-th optimal one. The base case is the exchange step. Then o(i+1) starts no earlier than o(i) ends, which is no earlier than g(i) ends, so o(i+1) was still available to greedy, which took the earliest finisher available. If the optimal schedule were longer, its next activity would also fit after greedy's last pick, so the counts are equal.
A check on the lab bookings: (10,11) (11,15) (15,16) (17,19) is another legal schedule of four. Its finish times are 11, 15, 16 and 19. Greedy's are 11, 13, 16 and 18, level or ahead at every position.
When neither proof goes through, look for a counterexample instead.
04Fails: coin change
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return countI compared this with dynamic programming, which finds the true minimum by building up from smaller amounts. For coins 25, 10, 5, 1 and amount 63, greedy gave 6 coins and DP also gave 6.
For coins 1, 3, 4 and amount 6, greedy takes 4, then 1, then 1, which is 3 coins. The best is 3 + 3, which is 2 coins. Checking every amount from 1 to 49 with these coins, greedy was wrong at 6, 10, 14, 18, 22, 26, 30, 34, 38, 42 and 46. One bad choice at the start can never be repaired. When greedy fails, dynamic programming is the usual fix.
The script below compares greedy with a bottom-up DP for amounts 1 to 99 on five coin systems.
def dp_coins(coins, amount):
best = [0] + [float("inf")] * amount # best[a] = fewest coins for a
for a in range(1, amount + 1):
best[a] = 1 + min(best[a - c] for c in coins if c <= a)
return best[amount]
for coins in [(25, 10, 5, 1), (1, 3, 4), (25, 20, 10, 5, 1),
(1, 7, 10), (1, 2, 5, 10, 20, 50, 100, 200)]:
bad = [a for a in range(1, 100) if greedy_coins(coins, a) != dp_coins(coins, a)]
first = f"first at {bad[0]}: {greedy_coins(coins, bad[0])} vs {dp_coins(coins, bad[0])}" if bad else ""
print(coins, f"wrong for {len(bad)} of 99", first)(25, 10, 5, 1) wrong for 0 of 99
(1, 3, 4) wrong for 24 of 99 first at 6: 3 vs 2
(25, 20, 10, 5, 1) wrong for 15 of 99 first at 40: 3 vs 2
(1, 7, 10) wrong for 27 of 99 first at 14: 5 vs 2
(1, 2, 5, 10, 20, 50, 100, 200) wrong for 0 of 99Two systems never failed in this range: the US-style 25, 10, 5, 1 and the 1, 2, 5, 10, 20, 50, 100, 200 series that euro cents follow. Adding a 20 to the US set breaks it. At 40, greedy pays 25 + 10 + 5 instead of 20 + 20. With 1, 7, 10, the amount 14 costs greedy 5 coins (10 and four 1s) against 2 sevens. Sets where greedy is always optimal are called canonical; test each set rather than assume it.
05The two properties, and when DP takes over
A greedy algorithm is correct when two things hold. First, the greedy-choice property: some optimal solution contains the greedy first choice, so taking it never rules out the best answer. Second, optimal substructure: after making the choice, what remains is a smaller problem of the same kind, whose optimal answer combines with the choice to give the overall optimum.
Dynamic programming needs the second property but not the first. That is why DP handles the 1, 3, 4 coin system and greedy cannot.
Knapsack shows the boundary. Take three items with (value, weight) of (30, 10), (50, 20) and (60, 30) and a capacity of 40. Ranked by value per unit of weight (3, 2.5 and 2), greedy takes the first two for a value of 80, and the third no longer fits. The best 0/1 answer is the first and third together, worth 90. If items can be cut, the same ranking is exactly right: both whole items plus a third of the last one give 100.
The warning sign is a choice whose cost shows up later, like a gap no item fills. DP survives it by keeping the best answer to every smaller subproblem.
06Classic greedy problems
Several famous algorithms are greedy, each with a proof. Dijkstra's shortest path always settles the nearest unsettled node (valid when edge weights are not negative). Kruskal's and Prim's minimum spanning tree algorithms add the cheapest safe edge. Huffman coding repeatedly merges the two least frequent symbols. Fractional knapsack takes items by value per weight.
The 22 characters of "deep sleep needs deeds" use seven distinct symbols, so a fixed-length code needs 3 bits each, 66 bits in all. Huffman coding needs 56 bits. The exact code lengths depend on how ties between equal counts are broken, but every tie-breaking order gives the same 56-bit total.
Jump game is a common interview version. Each value is the longest jump allowed from that index; can you reach the last index? Track the furthest index reachable so far, one pass and O(1) extra space.
def can_jump(nums):
reach = 0 # furthest index reachable so far
for i, n in enumerate(nums):
if i > reach:
return False # stuck before index i
reach = max(reach, i + n)
return True
print(can_jump([2, 0, 3, 0, 1, 2]), can_jump([1, 2, 0, 0, 3]))True FalseIn the second array the reach stalls at index 3.
07How to check an idea, and common pitfalls
Write a simple correct solution (brute force or DP) and compare on all small inputs, as I did for coin amounts 1 to 49. One mismatch is enough to reject the idea.
Here is that test for four interval rules that all sound reasonable. A brute-force solver checks every subset of 10 random intervals (starts 0 to 20, lengths 1 to 8) over 2,000 instances, counting how often each rule falls short.
import random
from itertools import combinations
def overlap(a, b):
return a[0] < b[1] and b[0] < a[1]
def greedy(ivs, key):
chosen = []
for x in sorted(ivs, key=key):
if not any(overlap(x, c) for c in chosen):
chosen.append(x)
return len(chosen)
def brute(ivs): # tries all 1,024 subsets
return max(r for r in range(len(ivs) + 1) for sub in combinations(ivs, r)
if not any(overlap(a, b) for a, b in combinations(sub, 2)))
random.seed(1)
losses = {"earliest finish": 0, "earliest start": 0, "shortest first": 0, "fewest overlaps": 0}
for _ in range(2000):
ivs = [(s, s + random.randint(1, 8)) for s in (random.randint(0, 20) for _ in range(10))]
rules = {"earliest finish": lambda x: x[1], "earliest start": lambda x: x[0],
"shortest first": lambda x: x[1] - x[0],
"fewest overlaps": lambda x: sum(overlap(x, y) for y in ivs if y != x)}
best = brute(ivs)
for name, key in rules.items():
losses[name] += greedy(ivs, key) < best
print(losses){'earliest finish': 0, 'earliest start': 887, 'shortest first': 110, 'fewest overlaps': 26}Earliest finish never lost. Shortest-first fails on a case as small as (0,5) (4,7) (6,11): it takes the short middle interval and blocks both others. Fewest overlaps sounds careful and failed only 26 times, about 1.3% of instances. Hand-made tests would likely miss it.
Pitfalls that cost marks: sorting by the wrong key or in the wrong direction, getting the boundary test (>= or >) wrong, trusting small sample tests, running Dijkstra with negative edges, and assuming every DP problem hides a greedy shortcut.
In interviews, name the greedy rule, say why it should be safe, and offer a small case that would expose a flaw. Interviewers care more about this reasoning than the code.
08Common interview questions
Q: What is a greedy algorithm?
A: One that makes the locally best choice at each step and never reconsiders it.
Q: How do you prove a greedy algorithm is correct?
A: With an exchange argument (swap the greedy choice into an optimal solution without making it worse) or by showing greedy stays ahead at every step.
Q: Why sort activities by finish time and not start time?
A: The earliest finish leaves the most room for the rest. In the lab-machine example, earliest start takes the four-hour booking (8,12) first and fits 3 bookings instead of 4.
Q: Give a case where greedy fails.
A: Coin change with coins 1, 3, 4 and amount 6: greedy uses 4 + 1 + 1, three coins, while 3 + 3 uses two.
Q: Why does greedy solve fractional knapsack but not 0/1 knapsack?
A: Splitting means filling by value per weight never wastes capacity. Without it, a gap can remain: in the example greedy gets 80, the best is 90.
Q: Greedy or DP?
A: Try greedy if a ranking rule seems natural, then hunt for a counterexample with brute force. If one appears, use DP.