Greedy Algorithms

What makes an algorithm "greedy"#

A greedy algorithm builds up its solution piece by piece, and at every single step, it picks whatever option looks best right now — without reconsidering earlier choices and without looking ahead to see how this choice affects the future.

Analogy: making change with the fewest coins by always grabbing the largest coin that still fits, then repeating — never once reconsidering a coin you already picked. That's the greedy mindset in a sentence: commit to the locally best-looking move, and never look back.

This makes greedy algorithms typically much simpler and faster than alternatives like dynamic programming, which (as the previous page showed) considers multiple possible choices at each step and combines their results. But that speed comes with a catch: greedy only produces the actually optimal answer when a problem has the greedy choice property — meaning a locally optimal choice at every step is provably guaranteed to lead to a globally optimal outcome overall. Not every problem has this property, and a greedy algorithm applied to one that doesn't will produce a wrong (suboptimal) answer, with no error and no warning that anything went wrong at all.

When greedy fails: a concrete counterexample#

Take coin change — given a set of coin denominations, make a target amount using as few coins as possible — with coins [1, 3, 4] and a target of 6.

def greedy_coin_change(coins, target):
    coins = sorted(coins, reverse=True)
    count = 0
    for coin in coins:
        while target >= coin:
            target -= coin
            count += 1
    return count if target == 0 else None

print(greedy_coin_change([1, 3, 4], 6))   # 3  ->  greedy picks 4, then 1, then 1

Greedy always grabs the largest coin that still fits: it takes a 4 first (leaving 2), then two 1s (leaving 0) — three coins total. But the actual optimal answer is two coins: 3 + 3 = 6. Greedy's "always take the biggest coin that fits" rule locks in the 4 immediately and has no mechanism to undo that choice once it becomes clear, two steps later, that it was a mistake.

This is exactly the shape of problem dynamic programming handles correctly — by considering the true optimal answer over all possible choices at each amount, and combining them, rather than committing irreversibly to whichever choice looks best in the moment. It's worth noting that everyday currency systems (U.S. coins: 1, 5, 10, 25) happen to be specially structured ("canonical") so that greedy does work correctly for them — but that's a property of those specific denominations, not something that holds for coin systems in general. This is exactly why "coin change" with an arbitrary set of denominations is taught as a dynamic programming problem, not a greedy one.

A complete worked example greedy DOES solve correctly: activity selection#

Problem: given a list of activities, each with a start and end time, select the maximum number of non-overlapping activities that a single resource (one room, one person) can attend.

Greedy strategy: sort activities by their end time, then repeatedly pick the next activity whose start time is at or after the end time of the last activity picked. The greedy choice — always take whichever remaining activity finishes earliest — provably leads to the optimal answer here, because finishing earliest always leaves the maximum possible remaining time for whatever comes next. (This can be proven with a standard "exchange argument": take any optimal solution that doesn't start with the earliest-finishing activity, and swapping it in never makes that solution worse — which is exactly the kind of guarantee coin change with [1, 3, 4] could not offer.)

def activity_selection(activities):
    # each activity is (start, end); sort by end time first
    activities = sorted(activities, key=lambda a: a[1])

    selected = [activities[0]]
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:            # doesn't overlap the last activity we selected
            selected.append((start, end))
            last_end = end

    return selected


meetings = [(1, 3), (2, 5), (4, 7), (1, 8), (6, 9), (8, 10)]
print(activity_selection(meetings))   # [(1, 3), (4, 7), (8, 10)]

Tracing it: sorted by end time, the meetings become (1,3), (2,5), (4,7), (1,8), (6,9), (8,10). Start with (1,3) selected, last_end=3. (2,5): start 2 < 3, overlaps, skip. (4,7): start 4 >= 3, select it, last_end=7. (1,8): start 1 < 7, skip. (6,9): start 6 < 7, skip. (8,10): start 8 >= 7, select it, last_end=10. Final selection: [(1,3), (4,7), (8,10)] — three non-overlapping meetings, and no other combination from this list can fit more than three.

This runs in O(n log n), entirely dominated by the initial sort — the selection pass itself is a single O(n) linear scan. Compare that to how much more work a problem without the greedy choice property would demand (dynamic programming's knapsack, from the previous page, needing O(n × capacity) to properly weigh every combination) — greedy's speed here is a direct reward for the problem actually having a provable greedy structure.

Distinguishing greedy-solvable problems from ones that need DP#

A practical rule of thumb: if you can convince yourself (ideally via an exchange argument, like activity selection's) that the locally best choice never forecloses a better overall combination, greedy is correct — and it'll typically be simpler and faster than DP. But if making the "obviously best" choice right now can rule out a better combination later — as [1, 3, 4] coin change demonstrated — that's a signal the problem needs to weigh multiple possibilities and combine them, which means reaching for dynamic programming instead. When you're unsure which camp a new problem falls into, trying to construct a small counterexample by hand (the way [1, 3, 4], target 6 was constructed above) is usually the fastest way to find out — before investing time in a greedy implementation that might quietly be wrong.

Common mistakes#

• Assuming greedy works because it produced a correct-looking answer on one or two test cases. Always look for (or try to disprove) the greedy choice property directly — don't just spot-check outputs, since a wrong greedy algorithm can still get lucky on small or convenient inputs.
• Sorting by the wrong key. Activity selection specifically requires sorting by end time — sorting by start time or by duration instead produces a plausible-looking algorithm that is not actually optimal.
• Assuming a greedy algorithm that works for one input distribution (standard currency denominations) generalizes to any input of a similar shape (arbitrary coin systems). The greedy choice property is a fact about the specific problem instance, not the general problem template.
• Adding backtracking or "undo" logic to a greedy algorithm. At that point it's no longer a pure greedy algorithm — if a solution needs to reconsider earlier choices, that's itself a sign the problem may call for dynamic programming instead.