Greedy Algorithms Explained: When Local Best Is Globally Best

A shopkeeper returns ₹87 in change. She doesn't deliberate: 50, then 20, then 10, then 5, then 2 — the biggest note that fits, every time. Five pieces, no planning, no reconsidering. And it happens to be the fewest pieces possible.

That instinct — take the locally best option, commit, never look back — is a greedy algorithm. When it works, it's the fastest, simplest thing on the menu. The catch, and the real subject of this lesson: the same instinct is sometimes confidently, provably wrong — and you must be able to tell which situation you are standing in.

The shape of a greedy algorithm

Almost every greedy solution is two lines of structure: sort by the right criterion, then sweep once, committing as you go. No recursion tree, no table, no undo. Costs follow: O(n log n) for the sort, O(n) for the sweep — when greedy is correct, nothing beats it.

All the risk hides in three words: the right criterion. And deeper: greedy correctness is a property of the problem, not the code — the problem must have the greedy-choice property: some locally best choice is always part of SOME optimal solution, so committing to it never closes the door.

A case where greedy provably wins

One auditorium, a list of requested events (start, end). Fit the maximum number of non-overlapping events.

Pause — three plausible criteria. Which would you sort by, and can you break the other two? (a) earliest start; (b) shortest duration; (c) earliest end.

Break (a): one day-long event starting at 9 am gets picked first and blocks everything. Break (b): a short event bridging two long ones kills both for the price of one. The survivor is (c): earliest END time — the event that frees the room soonest leaves maximum room for the future:

def max_events(events):
    events.sort(key=lambda e: e[1])       # by END time - the criterion
    taken, last_end = 0, float("-inf")
    for start, end in events:
        if start >= last_end:             # fits after the last taken
            taken += 1
            last_end = end                # commit, never revisit
    return taken

print(max_events([(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]))

3

Dry run: the room-booking sweep

sorted by end: (1,4) (3,5) (0,6) (5,7) (8,9) (5,9)

(1,4): 1 >= -inf  -> TAKE      last_end=4
(3,5): 3 >= 4 ?  no -> reject  (overlaps the taken one)
(0,6): 0 >= 4 ?  no -> reject
(5,7): 5 >= 4    -> TAKE      last_end=7
(8,9): 8 >= 7    -> TAKE      last_end=9
(5,9): 5 >= 9 ?  no -> reject

3 events: (1,4), (5,7), (8,9)

Note the >=: it allows back-to-back events (end 4, start 4). Using > silently forbids them — a spec question worth asking your interviewer out loud.

Why is it safe? The exchange argument

Greedy's standard proof shape, worth owning as one sentence. Take ANY optimal schedule. Its first event ends at some time t; the earliest-ending event ends at t' ≤ t. Swap it in: everything after still fits (it ends no later), and the count didn't drop. So there is always an optimal schedule starting with the greedy choice — repeat down the schedule, and greedy is never beaten.

You won't write formal proofs in interviews, but sketching an exchange argument in one sentence is exactly what "why does this work?" is asking for.

The same instinct, wrong answer

Now change one detail of the shopkeeper's world. Coins are {1, 3, 4} and she owes ₹6. Run her biggest-first instinct yourself before reading on.

greedy:  take 4 (biggest that fits) -> owe 2
         take 1 -> owe 1;  take 1 -> owe 0
         total: 3 coins  (4 + 1 + 1)

optimal: 3 + 3 = 6      total: 2 coins

Greedy is wrong — not slower, wrong. What broke? Taking the 4 stranded her at 2, which this coin system can only make as 1+1. The locally best first choice constrained the remainder into a bad position. With real denominations {1, 2, 5, 10, ...} each note efficiently covers the combinations below it, so grabbing the biggest never hurts — the greedy-choice property held there and silently failed here. Correctness lived in the data, not in the code.

Memorise this tiny counterexample verbatim — {1, 3, 4}, target 6 — it is the standard demonstration, and it is precisely the problem DP will solve correctly next lesson, by paying for the lookahead greedy refuses to buy.

The two-minute greedy test

Before trusting any greedy idea, run this checklist:

• 1. Hunt a counterexample, honestly. Small adversarial inputs: ties, extremes, one-big-vs-many-small. Two real minutes. One counterexample = greedy is dead; move to DP.
• 2. Sketch the exchange argument. "Any optimal solution can swap its first choice for mine without getting worse" — if you can say why, confidence is earned.
• 3. Check choice–future entanglement. Does my choice change what future choices are worth? Independence favours greedy; entanglement (the stranded ₹2) favours DP.

🎯 Selection-round radar: the question is rarely "write a greedy algorithm" — it's "would greedy work here, and why?", deliberately set on boundary problems (coin change, jump game, knapsack variants) to watch your testing process. Showing the counterexample hunt IS the answer.

One problem, both verdicts: the knapsack

A bag holds 10 kg; items have weights and values; steal the maximum value. One assumption flips the verdict:

Items divisible (rice, oil — any fraction): sort by value-per-kg, take greedily from the top, top up the last item fractionally. Provably optimal — the bag always fills with the densest available value. Greedy's cleanest win.

Items all-or-nothing (a TV — no half TVs): the same greedy fails. Capacity 10; item A (7 kg, ₹70 — ratio 10), items B and C (5 kg, ₹45 each — ratio 9). Greedy takes A... and strands 3 kg no item fits: total ₹70. Optimal takes B + C, filling the bag exactly: ₹90. Indivisibility means the ratio-best item can waste capacity — the stranded-remainder failure again.

Divisible → greedy; indivisible → DP (0/1 knapsack, lesson 8). One problem, one changed assumption, opposite tools — the cleanest picture of where greedy's border runs.

The greedy classics worth knowing

That last row deserves a beat: the most famous graph algorithms ARE greedy algorithms — proven safe once, by someone else, so the world uses them with confidence. That's the arrangement: greedy's speed, rented against a proof.

What if...?

What if two events tie on end time? Any order works — the exchange argument doesn't care which equal-ending event goes first. Ties break greedy only when your criterion was secretly incomplete; test with tied inputs.

What if I need WHICH events, not just how many? Collect them during the sweep (append instead of count). Greedy sweeps naturally produce the solution, not only its size.

What if the input is a stream — I can't sort? Most greedy algorithms lean on the sort; without it you often need a heap to keep serving the current best (that's what Dijkstra does live). "Greedy = sort + sweep, or heap + serve" covers both worlds.

What if my greedy passes all the given examples? Still not proof — setters choose examples where naive greedy survives, then hide the counterexample in the judge. The two-minute test exists precisely because examples are not arguments.

Common mistakes

• Trusting greedy because it feels natural — the {1, 3, 4} counterexample exists to break that feeling.
• Sorting by start time or duration in activity selection.
• Ratio-greedy on 0/1 knapsack — the stranded-capacity failure.
• Claiming optimality with neither a counterexample hunt nor an exchange sketch — "it passed my examples" is not an argument.
• Missing the >= vs > back-to-back decision.
• Using DP where greedy is proven — correct but slower, and it signals you don't know the classics.

How do I recognise greedy problems?

• Scheduling with a resource ("maximum events", "minimum platforms/rooms") → sort by the right time field and sweep.
• "Minimum number of X to cover/reach Y" → often a frontier greedy (jump game family).
• Ratio or density language ("per kg", "per unit") + divisibility → fractional greedy.
• The tell for NOT-greedy: a choice that changes the value of future choices — coin systems like {1, 3, 4}, all-or-nothing items → DP.

And whatever the story: run the two-minute test before writing a line. In interviews, run it audibly.

Quick revision

One thing to remember

Greedy is a claim, not a method — the claim that local best never hurts. Spend two minutes trying to break the claim before you trust it.

Practice Zone — PYQs from real selection rounds

Six MCQs, then three tasks: activity selection fully traced, breaking greedy with the coin counterexample, and the minimum-platforms sweep.

Q1Greedyeasy

A greedy algorithm is one that:

Asked in

aTries every possibility and keeps the bestbMakes the locally best choice at each step and never revisits itcUses the most memory availabledAlways sorts the input first

Q2Greedyeasy

For Indian denominations (₹1, 2, 5, 10, 20, 50, 100...), making ₹87 greedily (largest coin first) gives:

Asked in

a50 + 20 + 10 + 5 + 2 — five notes/coins, which is optimal hereb87 one-rupee coinscAn incorrect totald20 + 20 + 20 + 20 + 5 + 2

Q3Greedymedium

Activity selection (max number of non-overlapping meetings) sorts by:

Asked in

aStart time — take whatever starts firstbDuration — shortest meetings firstcEND time — always take the meeting that frees the room earliestdAny order works

Q4Greedymedium

Fractional knapsack allows greedy (by value/weight ratio) but 0/1 knapsack does NOT because:

Asked in

a0/1 knapsack has larger numbersbWhen items are indivisible, the ratio-best item can waste capacity that a different combination would use fully — a partial 'top-up' is forbiddencFractional knapsack is NP-harddGreedy works for both; DP is just faster

Q5Greedymedium

Jump Game: arr[i] = max jump length from i. For [2, 3, 1, 1, 4], the O(n) greedy tracks:

Asked in

aEvery possible path via recursionbThe farthest index reachable so far; if the scan ever passes it, return FalsecThe minimum elementdJumps of size 1 only

Q6Greedyhard

Which is the strongest evidence that greedy is WRONG for a given problem?

Asked in

aThe problem involves moneybYou can construct ONE counterexample where the locally best first choice leads to a worse final outcomecThe input is largedThe problem mentions optimisation

Hands-on tasks:

FAQ

You now know exactly where never-look-back is safe. Next: the tool for every problem where it isn't — Lesson 7: Dynamic Programming →