Greedy Algorithms: When Local Optimal Is Globally Optimal

Post #11’s min_coins exercise asked for the minimum number of coins to make a given amount, solved thoroughly and correctly using dynamic programming — considering every genuinely relevant possibility before committing to an answer. There is a dramatically simpler, faster strategy that works for this exact problem too, at least with the coin denominations most currencies actually use: at every step, just grab the largest coin that still fits. This is a greedy algorithm — and the fact that it works perfectly for US coins and fails outright for some other, entirely plausible sets of denominations is the single most important lesson in this post.

The Greedy Strategy

A greedy algorithm makes the choice that looks best right now, at each individual step, and never reconsiders that choice later — no backtracking, no exploring alternatives, no remembering other possibilities the way Post #11’s dynamic programming deliberately does. This is dramatically simpler and faster to compute than DP’s exhaustive approach — the genuine question this post answers is exactly when that simplicity comes at no cost, and when it silently produces a wrong answer.

Where Greedy Succeeds: US Coin Change

def greedy_coin_change(amount: int, denominations: list[int]) -> list[int]:
    denominations = sorted(denominations, reverse=True)  # largest first
    result = []
    for coin in denominations:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    return result

print(greedy_coin_change(67, [25, 10, 5, 1]))
# [25, 25, 10, 5, 1, 1] — 6 coins, and this genuinely IS the minimum possible for these denominations

At every step, this simply grabs the largest coin that still fits, commits to it, and never looks back — dramatically simpler than Post #11’s DP-based min_coins, and for standard US coin denominations (25, 10, 5, 1), it reliably produces the actual minimum number of coins, every single time.

Where Greedy Fails: Non-Standard Denominations

print(greedy_coin_change(6, [4, 3, 1]))
# [4, 1, 1] — 3 coins

# But the actual minimum is [3, 3] — only 2 coins!

The greedy approach grabs 4 first, because it’s the largest coin that fits under 6 — but that single choice makes the overall optimal solution ([3, 3]) impossible to reach, since after taking the 4, only 2 remains, and no combination of the remaining denominations reaches exactly 2 in fewer than two more coins. This is the entire lesson of this post, made concrete: the locally best-looking choice at each step is not always part of the globally best overall solution, and greedy algorithms have no mechanism to detect or correct for this — they commit and move on, exactly as designed.

Post #11’s dynamic programming approach, by contrast, genuinely considers every relevant combination and would correctly return [3, 3] for this exact input, precisely because it never commits to a single choice without comparing it against the alternatives.

When Greedy Actually Works: The Required Property

A greedy algorithm produces a guaranteed-correct, globally optimal answer specifically when a problem exhibits the greedy choice property: the locally optimal choice at each step is always part of some globally optimal solution — genuinely true for standard coin denominations (each coin value is enough larger than the sum of all smaller denominations combined that grabbing it greedily never blocks an eventually-optimal path), and genuinely false for the [4, 3, 1] counter-example above.

There is no simple, universal test for this property — it must be proven specifically for each problem, which is precisely why dynamic programming remains the safer, more broadly applicable default whenever you are not certain the greedy choice property genuinely holds for your specific problem and data.

A Second Example Where Greedy Succeeds: Activity Selection

“Given several activities, each with a start and end time, select the maximum number that can be attended without any overlapping.”

def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    activities = sorted(activities, key=lambda a: a[1])  # sort by END time
    selected = [activities[0]]
    last_end = activities[0][1]

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

    return selected

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

This greedy strategy — always picking the activity that ends soonest among the remaining valid options — is provably optimal for this specific problem: choosing whichever activity frees up your schedule earliest always leaves the maximum possible room for everything that comes after, a genuine instance of the greedy choice property holding true, unlike the non-standard coin denomination case above.

Greedy vs. Dynamic Programming: The Direct Comparison

The practical decision rule: reach for greedy specifically when you can actually prove (not merely hope) the greedy choice property holds for your specific problem — activity selection, standard currency coin change, and several other well-known classic problems genuinely have this property. When you are uncertain, or the problem’s structure resembles the failing coin-denomination example in this post, dynamic programming’s exhaustive-but-guaranteed-correct approach is the safer default.

Real-World Use Cases

Scheduling and resource allocation with the activity-selection structure: Meeting room booking, task scheduling with fixed time windows, and similar problems frequently map directly onto this post’s activity selection example.

Data compression: Huffman coding, a real, widely-used compression technique, relies on a provably correct greedy strategy for building an optimal encoding.

Network routing: Certain network path-finding algorithms use greedy strategies specifically in contexts where the greedy choice property has been mathematically proven to hold.

Currency systems, with the important caveat covered in this post: Real-world currency denominations are frequently, though not universally, designed in a way that makes greedy coin-making correct — a genuinely interesting, real-world design consideration worth knowing exists.

Common Mistakes and Gotchas

⚠️ Mistake 1: Assuming greedy works without verifying the greedy choice property Covered at length above — this is the single most important, most common mistake with greedy algorithms: applying the simple, fast strategy to a problem where it has not actually been shown to produce correct results, and getting a plausible-looking but genuinely wrong answer.

⚠️ Mistake 2: Assuming a greedy solution that works on your test cases works universally The [4, 3, 1] failure in this post only surfaces for specific amounts (like 6) — testing only with amounts where greedy happens to succeed can create false confidence in a genuinely broken general solution.

⚠️ Mistake 3: Defaulting to dynamic programming even when greedy’s correctness has been genuinely established The opposite mistake — for problems like activity selection, where the greedy choice property is proven, using DP’s more expensive exhaustive approach adds unnecessary complexity and cost for no correctness benefit.

⚠️ Mistake 4: Confusing “greedy” as a general description of code quality with the specific algorithmic technique “Greedy algorithm” in this post’s sense is a precise technical term describing this specific never-reconsider strategy — not a general critique of code that makes locally reasonable decisions without global awareness in some other, informal sense.

Quick Reference

# Greedy pattern: sort by some criterion, then make irrevocable local choices
def greedy_algorithm(items):
    items = sorted(items, key=some_criterion)
    result = []
    for item in items:
        if locally_valid(item, result):
            result.append(item)  # committed — never reconsidered
    return result

When greedy is safe: the greedy choice property has been proven for your specific problem (activity selection, standard coin denominations, Huffman coding, several other well-known classics).

When to default to DP instead: the greedy choice property is unproven, uncertain, or the problem structure resembles a known counter-example.

Exercises

Exercise 1 — Direct application Test greedy_coin_change from this post against several different amounts using the denominations [4, 3, 1], and identify at least two more specific amounts (besides 6) where the greedy result is not actually minimal.

Exercise 2 — Slight variation Modify activity_selection to also return the count of activities selected, and verify against the given example that no alternative selection of non-overlapping activities from the same input could produce a higher count.

Exercise 3 — Real-world combination Write both a greedy and a DP-based (from Post #11) solution to the coin-change problem, run both against several different denomination sets (including standard US coins and the failing [4, 3, 1] example), and print a comparison showing exactly where they agree and where they diverge.

Exercise 4 — Open-ended challenge Research one additional classic problem where greedy is known to fail despite seeming intuitively reasonable (a well-known example is the “0/1 knapsack problem,” where you cannot take fractional items) — explain, in your own words, specifically why the greedy choice property fails to hold for it.

FAQ

Q: How do I know in advance whether a greedy approach will work for a new problem I’m facing? A: There’s no shortcut — the greedy choice property must be genuinely proven (or found to be already proven in established literature, for well-known problems) rather than assumed from a few successful test cases; when in doubt, dynamic programming’s guaranteed correctness makes it the safer default.

Q: Is greedy ever used specifically because an approximate, “good enough” answer is acceptable, even when it’s not provably optimal? A: Yes, genuinely common in practice — for very large-scale problems where an exact DP solution would be too slow or memory-intensive, a greedy approximation is sometimes deliberately accepted, understanding explicitly that the result may not be perfectly optimal, in exchange for genuinely practical speed.

Q: Why did the US choose coin denominations that happen to make greedy work? A: This reflects genuine, deliberate design consideration in currency systems — denominations chosen so that a natural, greedy “grab the biggest bill/coin that fits” strategy also happens to be mathematically optimal, a real-world instance of the theoretical property covered throughout this post.

Q: Is greedy always faster than dynamic programming when both happen to produce correct results? A: Yes, essentially always — greedy’s single-pass, never-reconsider strategy is fundamentally less computational work than DP’s exhaustive consideration of possibilities, which is exactly why establishing the greedy choice property, when possible, is genuinely worth the extra proof effort for performance-critical applications.

Summary and Next Steps

You now understand greedy algorithms as a genuine, powerful bet: dramatically simpler and faster than Post #11’s dynamic programming, correct precisely when the greedy choice property holds for a specific problem, and silently, confidently wrong when it does not — exactly the failure mode this post’s [4, 3, 1] coin denomination example demonstrated concretely. This is not a criticism of greedy algorithms; it is the essential, precise understanding of their actual scope, which is what separates using them correctly from assuming they always work.

Your next step: Complete Exercise 1 — finding additional failing amounts for the [4, 3, 1] denomination set — since discovering more concrete failure cases yourself builds far more durable caution about verifying the greedy choice property than accepting this post’s single example alone.

This concludes Module 3 of this series — Big O notation, sorting, searching, recursion, dynamic programming, and greedy algorithms are all now covered, giving you a complete, precise vocabulary for reasoning about how efficiently code actually runs. The next module turns outward, from algorithms running on a single machine to how real-world systems — networks, databases, operating systems — actually work.

Last updated: August 2026.