Greedy: The Core Idea

A cashier owes you 68 cents and has coins of 25, 10, 5 and 1. Without thinking, she takes the biggest coin that fits, again and again: 25, 25, 10, 5, 1, 1, 1. Seven coins, and no other way uses fewer. She never went back to reconsider a coin she had already handed over.

That habit is a greedy algorithm: build the answer one step at a time, take the option that looks best right now, and never undo it. The code is usually a sort and a loop. The difficulty is knowing whether the habit is allowed — because on a different set of coins, the same cashier gives the wrong answer and nothing warns her.

This lesson is mostly about that second part. Writing greedy code takes a minute. Earning the right to write it — by proving the choice is safe or breaking it with a small input — is what interviewers test.

The picture: a cashier with a strange till

Here is the cashier's habit as code, next to the version that explores every option.

1def coin_change_greedy(coins: list[int], amount: int) -> int:2    """Largest coin first. Fast, and wrong for some coin sets."""3    used = 04    for coin in sorted(coins, reverse=True):5        take = amount // coin          # as many of this coin as fit6        used += take7        amount -= take * coin8    return used if amount == 0 else -191011def coin_change_dp(coins: list[int], amount: int) -> int:12    """Fewest coins, by trying every last coin for every smaller amount."""13    INF = amount + 114    best = [0] + [INF] * amount15    for value in range(1, amount + 1):16        for coin in coins:17            if coin <= value:18                best[value] = min(best[value], best[value - coin] + 1)19    return best[amount] if best[amount] != INF else -1

Trace the greedy version on coins [1, 3, 4] and amount 6:

Greedy returns 3. The dynamic programming (DP) version returns 2 (3 + 3). At amount 6, DP compares "use a 4 and solve 2" with "use a 3 and solve 3" and keeps the better one. Greedy never looks at the second branch, because 3 is not the largest coin. Run both on every amount up to 30 and greedy is wrong on 6, 10, 14, 18, 22, 26 and 30 — and silent every time.

This is the whole difference between the two techniques. Greedy commits; DP explores.

The last row is the dangerous one. A wrong DP usually crashes or times out. A wrong greedy returns a number, confidently, and you only find out when an interviewer hands you [1, 3, 4].

How to recognise it

Interviewers never say "use greedy". These are the signals:

• An optimisation with an obvious one-line rule. "Take the one that finishes first." "Take the biggest." "Go as far as you can." If a plausible rule jumps out, greedy is a candidate — and a suspect.
• Scheduling, covering or allocating. Meetings, arrows through balloons, fuel stops, cookies to children. This family has more correct greedy solutions than any other.
• The answer is a yes/no or a count, and a single pass feels enough. "Can you reach the end?" "What is the fewest number of…?"
• The constraints rule out DP. With n up to 10⁵ or 10⁶, an O(n²) DP is 10¹⁰ steps or more. If the answer must be O(n) or O(n log n), you cannot search the choices, so you must commit to them.

One test separates the problems where greedy is safe from the ones where it is not: does taking the locally best option ever close a door that a worse option would have left open? Taking the 4 left an awkward remainder of 2 — a door closed. Taking the earliest-finishing meeting leaves the most time for the rest — nothing closed.

How it works: the exchange argument

The exchange argument has three steps, and you can say it without any formal notation:

1. Take any optimal answer — one that does not make the greedy choice.
2. Swap the greedy choice in — replace the optimal answer's first differing choice with the greedy one.
3. Show nothing got worse — the result is still valid and just as good, so an optimal answer containing the greedy choice exists. Repeat for the next choice.

Apply it to interval scheduling: given meetings with start and end times, keep as many as possible with no two overlapping (a meeting may start exactly when another ends).

Three rules suggest themselves. Two die in seconds:

• Earliest start first. Meetings [1, 10], [2, 3], [4, 5], [6, 7]. The rule keeps [1, 10] and nothing else fits: 1 meeting. The three short ones fit together: 3.
• Shortest first. Meetings [1, 5], [4, 7], [6, 10]. The shortest is [4, 7], and it overlaps both others: 1 meeting. [1, 5] and [6, 10] fit together: 2.
• Earliest end first. Survives both inputs. Now prove it.

Let g be the meeting that ends earliest of all. Take any optimal schedule and let o be its first meeting. If o is g, done. Otherwise g ends no later than o — that is what "ends earliest" means. Every other meeting in the optimal schedule starts after o ends, so it also starts after g ends. Swap o for g: the schedule is still valid and has the same size, so it is still optimal. Repeat the argument on the meetings left after g, and greedy's whole answer is optimal.

The intuition behind the proof: the greedy choice is the one that constrains the future least. Ending earliest leaves the most room for everything after it. Use that sentence to find a candidate rule — but not to prove it. "Largest coin" also sounds like it constrains the future least (it leaves the smallest remainder), and it is wrong, because a smaller remainder is not always an easier one. Candidate from intuition, confirmation from the exchange argument, death by counter-example.

Variants

Almost every greedy interview problem takes one of these forms. Each problem lesson in this section is one row.

The bottleneck form needs no loop at all. In Task Scheduler, equal tasks must be at least n slots apart and you want the shortest schedule. The busiest task decides the shape: if it appears top times, it needs top − 1 blocks of n + 1 slots, then one final slot for each task tied at top. Tasks A A A A B B C with n = 2 give 3 × 3 + 1 = 10 slots, for example A B C A B _ A _ _ A. If there are more tasks than that frame, the gaps fill with real work and the answer is simply the number of tasks. The Heaps section works this problem in full, with the heap simulation and this formula side by side.

The templates

Template 1 — sort, then sweep. This is interval scheduling, the most reused greedy in interviews.

1def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:2    """Most intervals that can be kept with no two overlapping (touching is fine)."""3    kept = 04    last_end = float("-inf")5    for start, end in sorted(intervals, key=lambda iv: iv[1]):   # earliest end first6        if start >= last_end:          # fits after the last interval we kept7            kept += 18            last_end = end9    return kept

• sorted(..., key=lambda iv: iv[1]) is the whole algorithm. Sort by the end, because that is the choice the exchange argument proved safe.
• last_end = float("-inf") means "nothing kept yet". Never start it at 0 or −1: coordinates can be negative.
• start >= last_end decides whether touching counts as overlapping. Here it does not. Ask the interviewer; it changes one character.

Template 2 — smallest sufficient match. In Assign Cookies, each child has a greed value, each cookie has a size, a child is happy with a cookie at least as big as their greed, and each child gets at most one cookie. Make as many children happy as possible.

1def feed_children(greed: list[int], sizes: list[int]) -> int:2    """Most children satisfied; each child gets at most one cookie."""3    greed, sizes = sorted(greed), sorted(sizes)4    child = 0                          # the least greedy child still hungry5    for size in sizes:                 # smallest cookie first6        if child < len(greed) and size >= greed[child]:7            child += 1                 # smallest cookie that satisfies this child8    return child

Greed [4, 1, 2] and cookies [3, 1, 1] sort to [1, 2, 4] and [1, 1, 3]. Cookie 1 feeds the child with greed 1. The second cookie 1 is too small for greed 2 and is skipped. Cookie 3 feeds greed 2. Answer 2. The exchange argument in one sentence: if an optimal answer gives the least greedy child a bigger cookie, swap in the smallest cookie that fits — the bigger one is at least as useful to everyone else.

Complexity

Most greedy solutions are O(n log n) time because of one sort, then O(n) for the sweep. The running-value forms (Jump Game, Gas Station) need no sort and are O(n). Space is O(1) beyond the input, or O(n) if you sort a copy, as Python's sorted does.

If your "greedy" solution is O(n²), stop. It is probably a DP in disguise, and you should decide which one you are writing.

Where it goes wrong

1. Not checking. This is the costly one, because it loses the whole question, not a few minutes. A wrong greedy returns a believable number. The fix is a habit: before writing the loop, spend sixty seconds trying to break your rule with three or four elements and an awkward gap. [1, 3, 4] is the template for anything with denominations or weights.

2. Sorting by the wrong key. The sweep is right; the order it sees is wrong. Interval scheduling sorted by start keeps a long early meeting that blocks several short ones. Merging intervals sorted by end misses overlaps. The rule of thumb: when you are selecting or covering, sort by end; when you are merging, sort by start.

3. Problems that look greedy but need DP. A local choice that changes the shape of what is left — not only its size — needs DP.

4. Boundaries. Whether two ranges that touch overlap is a question, not an assumption. It is the difference between > and >= in every sort-and-sweep problem.

Before you write greedy code, run this diagnostic in order: state the rule in one sentence; try to break it in sixty seconds; say the exchange argument; check whether the constraints allow DP.