Greedy — when local optimum wins globally

Greedy is risky: it works only when the locally best choice provably can't paint you into a corner. When it works, it's elegant and fast (often O(n log n) for the sort). When it doesn't, you need DP.

Start here: what "greedy" really means

Before any code, get the mental picture. Picture climbing a hill in thick fog. You cannot see the summit, so at each step you simply walk in whatever direction goes up the steepest right where you stand. That is greedy: each move is the best one visible from the current spot, decided with zero foresight and never undone. Sometimes that fog-walk lands you on the true summit; sometimes it strands you on a small bump (a "local maximum") with the real peak still far off. The whole skill of this lesson is telling those two cases apart before you trust the walk.

Let's nail down the vocabulary precisely, because interviewers use these exact words:

• A greedy algorithm builds an answer one decision at a time, and at each decision it commits to the option that looks best by some simple, fixed rule — then it moves on and never revisits that decision.
• A locally optimal choice (also called the "greedy choice") is the single best-looking option at the current step only, judged by your rule — for interval scheduling that rule is "the interval that finishes earliest among those still available."
• A globally optimal solution is the best possible answer across the whole problem. Greedy is "correct" exactly when stacking up locally optimal choices always reproduces a globally optimal solution.
• The greedy-choice property is the formal name for the thing that has to be true for greedy to work: there is always a globally optimal solution that contains the greedy (locally best) choice. If that holds at every step, you can keep taking the greedy choice and never lose.
• Optimal substructure is the companion property: after you make the greedy choice, what remains is a smaller problem of the same kind, and an optimal solution to that smaller piece, plus your greedy choice, is an optimal solution to the whole. (Dynamic programming needs this too — the difference is that greedy commits to one choice immediately, while DP keeps all choices open.)

A second worked example where greedy works: coin change with canonical coins

The interval walk above shows greedy on scheduling; here is greedy on a different shape of problem so the pattern sticks. Coin change asks: given coin denominations and a target amount, use the fewest coins that sum to the target. The greedy rule is the obvious one — repeatedly take the largest coin that does not overshoot the remaining amount. For real-world ("canonical") currency systems like US coins [25, 10, 5, 1], this greedy rule is provably optimal. Let's trace making 41 cents:

# coins = [25, 10, 5, 1], amount = 41, take largest that fits each step
# step 1  remaining 41: largest coin <= 41 is 25  -> take 25, remaining 16, coins used [25]
# step 2  remaining 16: largest coin <= 16 is 10  -> take 10, remaining  6, coins used [25,10]
# step 3  remaining  6: largest coin <=  6 is  5  -> take  5, remaining  1, coins used [25,10,5]
# step 4  remaining  1: largest coin <=  1 is  1  -> take  1, remaining  0, coins used [25,10,5,1]
# done: 4 coins (25 + 10 + 5 + 1 = 41) — and 4 is the true minimum

Why is grabbing the biggest coin safe here? Because of how these denominations nest: any solution that uses smaller coins where a 25 would have fit can be rewritten to use the 25 without increasing the coin count (for example, two 10s and a 5 — three coins — covering 25 can be swapped for a single 25). That is an exchange argument again, and it only holds because the coin values line up so neatly. Change one value and the property can vanish — which is exactly the cautionary example next.

A worked example where greedy FAILS: coins {1, 3, 4} making 6

Now keep the same greedy rule — "take the largest coin that fits" — but change the denominations to [4, 3, 1] and make the amount 6. Watch greedy walk straight into a worse answer:

# coins = [4, 3, 1], amount = 6, GREEDY rule: take largest that fits
# step 1  remaining 6: largest coin <= 6 is 4  -> take 4, remaining 2, coins used [4]
# step 2  remaining 2: largest coin <= 2 is 1  -> take 1, remaining 1, coins used [4,1]
# step 3  remaining 1: largest coin <= 1 is 1  -> take 1, remaining 0, coins used [4,1,1]
# greedy result: 3 coins  (4 + 1 + 1 = 6)

# BUT the true optimum is 2 coins: 3 + 3 = 6
# greedy's first grab (the 4) was the trap — it left an awkward 2 that needs two 1s

This is the whole danger of greedy in one picture. The locally optimal choice (the biggest coin, 4) felt obviously right, but it destroyed the chance to use two 3s — a counterexample, meaning a single concrete input where the greedy rule provably gives a worse answer than the true optimum. A counterexample is the fastest, most convincing way to disprove a greedy idea: you do not need theory, just one input where greedy loses. Here the greedy-choice property simply does not hold, because taking the 4 is not part of any optimal solution for amount 6. The correct tool for arbitrary coin sets is dynamic programming, which considers all coins at each amount instead of committing to the biggest:

def coin_change(coins, amount):       # DP — correct for ANY coin set
    best = [0] + [float('inf')] * amount   # best[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount] if best[amount] != float('inf') else -1

For coins = [4, 3, 1], amount = 6 this DP returns 2 (the 3 + 3 answer greedy missed), because it never throws away an option — it computes the best way to make every smaller amount first, then reuses those results. That extra bookkeeping is the price of correctness when the greedy-choice property fails.

Greedy vs. DP: how to tell which one a problem needs

Both greedy and dynamic programming build answers from sub-answers, so it is easy to confuse them. The dividing line is simple to state: greedy commits to one choice at each step and never looks back; DP keeps every choice open and lets the best one win at the end. Greedy is faster and simpler when it is allowed, because it explores exactly one path; DP is slower (it explores many overlapping subproblems) but it is safe even when a local choice could mislead.

A reliable habit under interview pressure: propose the greedy rule out loud, then immediately try to break it with a small adversarial input. If you can build a counterexample in a minute, switch to DP. If you genuinely cannot, sketch the exchange argument and proceed with greedy — explaining why it is safe is what separates a correct answer from a lucky one.

How to argue correctness: the exchange argument in plain terms

The exchange argument is the standard way to prove a greedy choice is safe, and it is much less scary than it sounds. The idea: assume someone hands you a perfect (optimal) solution that does not start with your greedy choice, then show you can swap in your greedy choice without making the solution any worse. If every optimal solution can be nudged toward the greedy one for free, then a fully greedy solution must itself be optimal. In three plain steps:

• 1. Assume an optimum exists that disagrees with greedy at the first place they differ.
• 2. Exchange the optimum's choice at that spot for greedy's choice, and argue the result is still valid and no worse (same count, same total, still feasible).
• 3. Repeat / induct: each swap makes the optimum agree with greedy one more step, and never loses quality — so greedy ends up at least as good as the optimum, i.e. optimal.

For interval scheduling, the swap is concrete: replace the optimum's first meeting with the earliest-finishing one. Since the earliest-finisher frees the room no later than whatever the optimum picked, every remaining meeting in the optimum still fits — the count cannot drop. That single observation, repeated, is the whole proof. You do not need to write formal induction in an interview; saying "swapping in the earliest-finisher never frees the room later, so no meeting is lost" is the exchange argument, and it is exactly what an interviewer wants to hear.

Recognition signals and pitfalls

Greedy problems tend to announce themselves. Train your ear for these prompts, and for the traps that make a plausible greedy rule wrong.

def max_intervals(intervals):
    intervals.sort(key=lambda x: x[1])   # sort by END time
    end = -float('inf'); count = 0
    for s, e in intervals:
        if s >= end:
            count += 1; end = e
    return count

Prove the greedy interval-scheduling rule — write max non-overlapping meetings: