Greedy Algorithms
15 min
A greedy algorithm builds a solution by always making the choice that looks best right now, never reconsidering it later. That's cheap — often O(n log n), usually just a sort plus one pass — but only correct for problems where the locally-best choice is provably part of some globally- best solution.
Activity selection is the textbook example where greedy works: given a set of intervals, pick the maximum number that don't overlap. Sorting by end time and always taking the next interval that starts after the last one you picked ends is provably optimal.
def max_activities(intervals):
intervals = sorted(intervals, key=lambda x: x[1])
count = 0
last_end = float("-inf")
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
Sorting by end time (not start time!) is the key insight — it always leaves the most room for whatever comes next.
Greedy doesn't always give the optimal answer — that's the trade-off for
its speed. Making change with US coins ([25, 10, 5, 1]) happens to work
greedily because of how those denominations are structured, but with coins
like [1, 3, 4] for amount 6, greedy picks 4 + 1 + 1 (3 coins) while
the true optimum is 3 + 3 (2 coins). When you're not sure greedy is
correct for a problem, dynamic programming (previous module) is the safe,
always-correct fallback — at the cost of more time and memory.
Write a function `max_activities(intervals)` that returns the maximum number of non-overlapping intervals selectable from `intervals` (a list of `(start, end)` tuples). Use the greedy 'earliest end time first' strategy.
Write a function `min_coins_greedy(coins, amount)` that returns the list of coins used to make `amount`, greedily taking the largest coin from `coins` (given sorted descending) that still fits, repeatedly.
What is the key risk of a greedy algorithm compared to dynamic programming?
You can implement a greedy algorithm for interval scheduling and coin-making, and know when greedy can silently give a wrong answer.