Greedy algorithms — and when the locally best choice isn't enough

A greedy algorithm makes the best-looking choice at each step and never looks back — sometimes that's provably optimal, and sometimes it's a plausible-looking wrong answer, which is exactly why knowing the difference matters.

Intermediate

5 min read

What "greedy" actually means as a strategy

A greedy algorithm builds a solution one step at a time, always picking whatever looks best right now, and never reconsidering that choice later. This is the opposite of dynamic programming's approach (from its own lesson): DP explores multiple possibilities and keeps whichever subproblem results actually lead to the best overall answer; greedy commits immediately to the locally-best option and moves on, never backtracking to check whether an earlier choice was actually a mistake.

A case where greedy provably works: making change

def min_coins_greedy(amount, denominations):
    denominations = sorted(denominations, reverse=True)
    count = 0
    for coin in denominations:
        count += amount // coin
        amount %= coin
    return count
 
min_coins_greedy(41, [25, 10, 5, 1])   # 25 + 10 + 5 + 1 = 4 coins — correct and optimal

Given US coin denominations, always taking the largest coin that fits happens to produce the true minimum number of coins, every time — greedily grabbing the biggest coin at each step never leads to a worse overall answer than some smarter alternative would have found. This works because of a specific property of this particular set of denominations (each is a large enough multiple of the ones below it) — it is not a general fact about "making change" as a problem.

A case where the exact same greedy strategy silently fails

denominations = [1, 3, 4]
min_coins_greedy(6, denominations)   # greedy: 4 + 1 + 1 = 3 coins
# actual optimal: 3 + 3 = 2 coins — greedy is WRONG here

With denominations [1, 3, 4], greedily grabbing the largest coin that fits (4) leaves 2, which then greedily takes two 1s — three coins total. But 3 + 3 = 6 uses only two coins, and there was no way for the greedy approach to discover that, because taking the 4 first was locally correct (it's the largest coin that fits) while being globally wrong. This is the entire danger of greedy: it can look completely reasonable at every single step and still land on the wrong final answer, with nothing about the algorithm's own execution ever signaling that it went wrong.

A case where greedy is provably always correct: activity selection

def max_activities(activities):
    # activities: list of (start, end) tuples
    activities = sorted(activities, key=lambda a: a[1])   # sort by END time
    selected = []
    last_end = float("-inf")
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected
 
max_activities([(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)])
# [(1, 4), (5, 7), (8, 9)] — the maximum number of non-overlapping activities

Given a set of activities each with a start and end time, and one resource that can only host one at a time, always picking the activity that ends earliest among the remaining valid options is provably optimal — it leaves the most possible room for future activities, since no other valid choice could free up the resource any sooner. Unlike the [1, 3, 4] coin problem, this greedy strategy is mathematically guaranteed correct for every possible input, not just a lucky-case coincidence — the proof (an "exchange argument": any optimal solution can be modified to include the earliest-ending activity without making it worse) is exactly what separates a greedy algorithm that's always right from one that merely often looks right.

The actual skill: knowing which kind of problem you're facing

Both are legitimate, useful algorithmic strategies — the actual skill is recognizing which shape a given problem has, before reaching for one. A common, real mistake is assuming greedy always needs to be proven wrong through testing ("let me just try it and see") — the correct approach is proving (or finding a known reference for) whether the problem has the specific structural property that makes locally-optimal choices compose into a globally-optimal one, the same exchange-argument style of reasoning behind the activity-selection example.

Other well-known greedy algorithms, briefly

Dijkstra's shortest path (mentioned in the graphs lesson) — greedily picks the closest unvisited node at each step, using a priority queue (from the heaps lesson) to always find that closest node efficiently. Provably correct specifically because edge weights are non-negative — the same greedy idea fails once negative edge weights are allowed.
Huffman coding (data compression) — greedily merges the two least-frequent symbols at each step to build an optimal-length encoding tree.
Fractional knapsack — greedily takes the highest value-per-weight item first; provably optimal specifically because items can be split fractionally, unlike the "0/1 knapsack" variant (whole items only), which is a genuine dynamic programming problem instead.

The pattern across all of them: each one has a specific, provable reason the greedy choice never needs revisiting — that proof is the actual content of "this greedy algorithm works," not just an observation that it happened to work on a few test cases.