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 need a correctness proof before trusting its optimality; tests can only find counterexamples — 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 I look for an exchange-argument proof. Brute-force checks on small inputs are useful for finding counterexamples and implementation bugs, but finite tests do not prove optimality for all inputs.

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)]))   # 2: (1,3), (4,7)
# 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