Greedy Algorithms
Make the locally best choice and never look back: when that is provably optimal and when it quietly fails. Covers interval scheduling, the exchange argument, a coin-change counterexample and fractional knapsack.
Taking the best thing in front of you
You are a conference room scheduler. Eight teams have asked for the room today, each for a fixed time window, and no two meetings may overlap. You want to fit in as many meetings as possible. How do you decide?
Most people reach for one of three instincts. Take the meeting that starts earliest. Take the shortest meeting, since short ones leave more room. Or take whichever ends earliest, so the room frees up soonest. Each sounds reasonable. Exactly one of them is guaranteed to give the best answer, and the other two have simple counterexamples. That gap between "sounds right" and "provably right" is the entire subject of greedy algorithms.
An algorithm that builds a solution step by step, at each step committing to the choice that looks best right now according to a fixed rule, and never reconsidering. It is correct only when a local best choice can be shown to be part of some globally optimal solution.
The shape of a greedy solution
Greedy algorithms share a rhythm: sort or prioritise the candidates by a rule, scan them once, and keep each candidate that is compatible with what you have already taken. That makes them fast (usually dominated by the sort, so O(n log n)) and short to write. It also makes them dangerous, because the code never tells you whether the rule is right.
Compare this with dynamic programming, which considers all the ways to split a problem and keeps the best. Greedy considers one way, the one the rule picks. When greedy is correct it is the cheaper tool; when it is wrong it returns a confident, plausible, suboptimal answer with no error message. So the real work in a greedy problem is never the loop. It is the justification.
Worked example: scheduling the most meetings
The winning rule is earliest finish time. Sort the meetings by end time. Take the first one. Then repeatedly take the next meeting whose start is at or after the end of the last one you took.
Why is that safe? Use an exchange argument, the standard proof technique for greedy algorithms. Imagine some optimal schedule that starts with a different meeting X. The meeting G that ends earliest overall finishes no later than X does. So swap X for G: G conflicts with nothing X did not already conflict with, the schedule is still valid, and it still has the same number of meetings. Therefore some optimal schedule starts with G. Remove G and everything it blocks, and the same argument applies to what is left. Repeat, and the greedy schedule is optimal.
The other two instincts fail on tiny inputs. Earliest start loses to one very long meeting that begins first and blocks everything. Shortest first loses when a short meeting straddles two otherwise compatible ones.
time -> 0 2 4 6 8 10 A [=================] <- starts first, but huge B [====] C [====] D [====] earliest-start picks A : 1 meeting earliest-finish picks B, C, D : 3 meetings
1meetings = [("Long", 0, 10), ("Short", 4, 6), ("Early", 1, 5), ("Late", 5, 9)]23def schedule(meetings, key):4 chosen, last_end = [], -15 for name, start, end in sorted(meetings, key=key):6 if start >= last_end:7 chosen.append(name)8 last_end = end9 return chosen1011rules = [12 ("earliest start", lambda m: (m[1], m[2])),13 ("shortest first", lambda m: (m[2] - m[1], m[1])),14 ("earliest finish", lambda m: (m[2], m[1])),15]16for label, key in rules:17 picked = schedule(meetings, key)18 print(label.ljust(16), picked, "->", len(picked), "meetings")
earliest start ['Long'] -> 1 meetings shortest first ['Short'] -> 1 meetings earliest finish ['Early', 'Late'] -> 2 meetings
When greedy fails: coin change
Making change feels like the poster child for greedy: always hand over the largest coin that fits. With US coins (25, 10, 5, 1) it is optimal, so the habit forms. But the rule is not a law of arithmetic. It works because of how those particular denominations relate to each other.
Change the coin system to 1, 3 and 4, and ask for 6. Greedy takes 4, then cannot use 4 again, takes 1 and 1: three coins. The optimal answer is 3 + 3, two coins. The local choice (take the biggest) trapped the algorithm in a branch from which the best answer was no longer reachable. A greedy choice is only valid if it can never rule out an optimal solution. Here it can.
The lesson is not "avoid greedy". It is: never trust a greedy rule without either a proof or a brute-force comparison on small cases. Writing a ten-line brute force and testing both on all small inputs is one of the cheapest bug-finders in algorithm work.
A matching result on a few examples proves nothing. Greedy on a coin system can be right for every amount except one. Compare against a slower, obviously correct method over a whole range of inputs.
1def greedy_coins(coins, amount):2 count = 03 for coin in sorted(coins, reverse=True):4 count += amount // coin5 amount %= coin6 return count78def best_coins(coins, amount):9 best = [0] + [None] * amount10 for a in range(1, amount + 1):11 options = [best[a - c] + 1 for c in coins if c <= a and best[a - c] is not None]12 best[a] = min(options) if options else None13 return best[amount]1415for coins, amount in [([25, 10, 5, 1], 63), ([4, 3, 1], 6), ([9, 6, 1], 12)]:16 print(coins, amount, "greedy:", greedy_coins(coins, amount), "optimal:", best_coins(coins, amount))
[25, 10, 5, 1] 63 greedy: 6 optimal: 6 [4, 3, 1] 6 greedy: 3 optimal: 2 [9, 6, 1] 12 greedy: 4 optimal: 2
A pair that shows the boundary: fractional versus 0/1 knapsack
You have a bag with capacity 50 and three items: weights 10, 20, 30 worth 60, 100, 120. If you may take fractions of an item (think flour, not laptops), greedy works beautifully: sort by value per unit weight and fill the bag, cutting the last item if needed. If every item must be taken whole or not at all, the same rule can fail, and you need dynamic programming.
The contrast is instructive. Fractions make every choice reversible in effect, since you can always take a bit less, so the local best never blocks the global best. Indivisible items make a choice final and chunky, which is exactly the kind of structure where a locally attractive choice can ruin the whole.
1items = [(10, 60), (20, 100), (30, 120)] # (weight, value)2capacity = 5034# Fractional knapsack: greedy by value density is optimal5total, room = 0.0, capacity6for weight, value in sorted(items, key=lambda it: it[1] / it[0], reverse=True):7 take = min(weight, room)8 total += value * take / weight9 room -= take10print("fractional greedy:", total)1112# 0/1 knapsack: the same density rule, items taken whole13total, room = 0, capacity14for weight, value in sorted(items, key=lambda it: it[1] / it[0], reverse=True):15 if weight <= room:16 total += value17 room -= weight18print("0/1 density greedy:", total)1920# 0/1 knapsack: exact answer by dynamic programming21best = [0] * (capacity + 1)22for weight, value in items:23 for w in range(capacity, weight - 1, -1):24 best[w] = max(best[w], best[w - weight] + value)25print("0/1 optimal:", best[capacity])
fractional greedy: 240.0 0/1 density greedy: 160 0/1 optimal: 220
A recipe for evaluating a greedy idea
Before you commit to a greedy solution, run it through four quick checks. First, state the rule in one sentence, with tie-breaking. Second, hunt for a counterexample on inputs of size three or four; most wrong greedy rules die there. Third, try the exchange argument: take any optimal solution that disagrees with the greedy first choice and show you can swap in the greedy choice without making things worse. Fourth, check the structure remains the same after the choice: once you commit, the remaining problem should be a smaller instance of the same kind.
Problems where greedy is the intended answer include interval scheduling, minimum spanning trees (Kruskal and Prim), shortest paths with non-negative weights (Dijkstra), Huffman coding and fractional knapsack. All of them have a proof that the local choice is safe. Dijkstra gets its own lesson in this series.
If a problem asks for "the minimum number of ..." or "the maximum number of ..." over a sequence of choices, try greedy first for a minute with a sorting rule, then immediately try to break it. If you can break it, move to dynamic programming.
Check your understanding
Each question has a trap that mirrors a real mistake.
In interval scheduling, which greedy rule guarantees the maximum number of non-overlapping meetings?
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Greedy loop | for item in sorted(items, key=rule):
if compatible(item, chosen): chosen.append(item) |
| Interval scheduling rule | sort by end time; take if start >= last_end |
| Fractional knapsack rule | sort by value / weight, descending |
| Proof technique | exchange argument: swap greedy choice into any optimal solution |
Common Pitfalls & Developer Mistakes
Trusting a greedy rule because it works on the samples
Why it happens: Samples are usually friendly. The rule may fail on one input that your examples do not contain.
Sorting by the wrong key in interval problems
Why it happens: Sorting by start time or length feels natural but is not optimal for maximising the count.
Forgetting tie-breaking
Why it happens: Equal keys can change which element is taken and, in some problems, the final answer.