Greedy: Take the Best Now, Hope It Holds

"Greedy is the most seductive paradigm: grab the best-looking option right now and never look back. Sometimes that's provably optimal. Often it's confidently, silently wrong — and the danger is exactly that it looks right."

The Greedy Move

A greedy algorithm builds a solution by repeatedly making the choice that looks best at this moment, committing to it, and never reconsidering. It's fast, simple, and uses almost no memory. The catch: this only produces the globally optimal answer for problems with a special structure — the greedy-choice property, where a locally optimal choice is always part of some globally optimal solution. When that property holds, greedy is beautiful. When it doesn't, greedy gives a plausible-looking wrong answer.

When Greedy Provably Works

Several famous algorithms are greedy and provably optimal: activity selection (to attend the most non-overlapping meetings, always pick the one that finishes earliest), Huffman coding (merge the two least-frequent symbols), Kruskal's and Prim's MST (cheapest safe edge), Dijkstra (closest unfinalized node), and fractional knapsack (highest value-per-weight first). In each, there's a proof — usually an exchange argument showing any optimal solution can be rearranged to include the greedy choice without getting worse. The greediness isn't a gamble there; it's been verified.

When Greedy Lies

And here's the trap. Coin change with arbitrary coins: making 6 from {1, 3, 4}, greedy grabs 4 then 1 then 1 (three coins), but 3+3 is two. 0/1 knapsack (each item taken whole or not): greedily taking the highest value-per-weight can overlook a better combination. These problems lack the greedy-choice property, so the locally-best choice paints you into a corner. The lesson: greedy's speed makes it tempting to assume it's correct, but you must prove it (or test exhaustively) before trusting it — an unproven greedy is a bug waiting for the input that exposes it.

Greedy makes the locally-best choice and never reconsiders — fast and simple, but optimal only when the greedy-choice property holds (proven via an exchange argument). It's correct for MST, Huffman, Dijkstra, activity selection; wrong for arbitrary coin change and 0/1 knapsack. Prove it; never assume it.

Pippa's Confession

I shipped a greedy coin-change solution because it passed every test I bothered to write — all using normal coin denominations, where greedy happens to work. Then a custom currency in the data ({1,3,4}) made it return suboptimal answers, silently. Dad's rule landed hard: "Greedy is a conjecture until you prove it. Looking right isn't being right." Now when a greedy solution tempts me, I either find the exchange-argument proof or brute-force-check it against small inputs before I trust a single result.

Code

Greedy that works (activity selection) vs fails (coin change)·python

# GREEDY THAT WORKS: activity selection. To attend the most non-overlapping
# meetings, always pick the one that FINISHES earliest. Provably optimal.
def max_activities(intervals):
    intervals.sort(key=lambda x: x[1])    # sort by finish time
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:             # doesn't overlap the last chosen one
            count += 1
            last_end = end                # greedily commit to this one
    return count

print(max_activities([(1,3),(2,5),(4,7),(1,8),(5,9)]))   # 3
# Finishing earliest leaves the most room for later meetings — and there's a
# proof (exchange argument) that this local choice is always globally optimal.

# GREEDY THAT FAILS: coin change with coins {1, 3, 4}, making 6.
def greedy_coins(coins, amount):
    coins.sort(reverse=True)
    used = 0
    for c in coins:
        used += amount // c; amount %= c
    return used
print(greedy_coins([1, 3, 4], 6))   # 3  (4+1+1) — WRONG, optimal is 2 (3+3)
# Greedy looked reasonable and was silently suboptimal. No greedy-choice property.

Exercise

For activity selection, explain why 'pick the meeting that finishes earliest' beats 'pick the shortest meeting' or 'pick the one that starts earliest' (give a counterexample where those alternatives fail). Then find a coin set and amount where the greedy 'take the biggest coin' gives more coins than optimal, proving greedy isn't safe there.

Hint

Earliest-finish leaves maximum room; 'shortest' can pick a short meeting that straddles two others and blocks both; 'earliest-start' can pick one long meeting that hogs the day. Greedy coin failure: coins {1,3,4}, amount 6 → greedy 4+1+1=3 coins, optimal 3+3=2 coins.

The Greedy Move

When Greedy Provably Works

When Greedy Lies

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0