Greedy

1 · Why greedy is dangerous and fast

Greedy is the strangest pattern in the toolkit. When it works, the solution is six lines, the runtime is the best you can hope for, and the proof is a paragraph. When it doesn't work, the bug is invisible. The code passes the visible test cases, looks correct under scrutiny, and silently returns the wrong answer on the adversarial input the grader picks. That asymmetry is the greediness paradox: greedy answers are easy to write and hard to prove correct, in roughly the same proportion that they are tempting and dangerous.

The senior-interview signal here is not whether you can write a greedy loop. Anyone can write a greedy loop. The signal is whether you can tell in advance whether the greedy choice is provably optimal, and whether you reach for DP instead when it isn't. That decision is what separates the candidate who delivers the right algorithm from the candidate who delivers a plausible one.

• When greedy is right, it's irresistible. The code is shorter than the DP equivalent, the runtime is usually O(n log n) dominated by a sort, and the memory is O(1) instead of O(n) or O(n²). On the right problems, greedy is strictly better than DP on every axis. Interval scheduling, Huffman coding, Kruskal's MST are textbook examples — DP works, but greedy works in fewer lines and runs faster.
• When greedy is wrong, the failure is silent. A wrong greedy rule typically passes 80–90% of test cases. Weighted interval scheduling, 0/1 knapsack, longest increasing subsequence: all look like they should yield to "sort and pick the best each step", and all silently produce sub-optimal answers on carefully chosen inputs. There's no error message, no out-of-bounds, no obvious symptom. Just a wrong number on test 17.
• The recognition is in the proof, not the code. Most patterns are recognised by the shape of the input (sorted? tree? graph?). Greedy is recognised by whether you can construct a proof (an exchange argument or a matroid structure) that the local choice is globally safe. If you can sketch the proof in your head, greedy is the right tool. If you can't, treat that as evidence the greedy is wrong.

The proof-of-correctness reflex

Every greedy claim should be backed by an exchange argument or a matroid-style proof before you commit to writing the loop. The reflex looks like this, said aloud:

1. State the greedy choice in one sentence. "At each step, pick the interval with the earliest finish time among those still compatible." If you need a paragraph, the rule is probably ambiguous and the proof will be hard.
2. Sketch the exchange argument. "Suppose OPT differs from GREEDY at the first step. Swap OPT's first choice for GREEDY's. The result is still valid and no worse." If you can't write that swap argument cleanly, the rule probably isn't optimal.
3. Stress-test with an adversarial input. Try to construct a small input (n = 3 to 5) where your greedy gives the wrong answer. If you find one, the greedy is broken; switch to DP. If you can't find one after a minute of trying, that's evidence (not proof) the greedy is right.
4. If the proof doesn't go through, suspect DP. The fallback for every "this feels greedy but I can't prove it" problem is dynamic programming. The recurrence is usually obvious once you accept that you can't commit to a single local choice — you have to keep all candidate choices alive until the end.

2 · How to recognise it

Greedy tends to fit problems where each step has an obvious-looking local choice and the problem hints at minimising or maximising a count. The general signals first, then five concrete shapes that recur:

• "Choose one of many" at each step. The problem asks you to make a sequence of decisions and each decision has a candidate that seems locally best (earliest deadline, shortest job, highest ratio).
• Sorting by a single attribute makes the structure obvious. Sort by start time, end time, deadline, value-to-weight ratio, frequency. If sorting clarifies the problem, greedy is usually worth a try.
• "Minimum number of X" or "maximum X you can do". Minimum number of intervals to remove, maximum number of tasks scheduled, fewest jumps, largest set. Counting problems with a natural ordering are greedy territory.
• No overlapping subproblems. If the same subproblem doesn't repeat, DP is overkill; a single forward sweep with a greedy rule is often enough.
• You can describe the choice in one sentence. "Always take the interval that ends earliest among those still compatible." If the rule needs a paragraph, it's probably not greedy.

Shape A: activity scheduling (sort by end time)

• Tell. "Maximum number of non-overlapping intervals", "minimum intervals to remove so the rest don't overlap", "fit the most meetings into one room". Each input is an interval with a start and end time.
• The rule. Sort by end time. Greedily pick the next interval whose start is ≥ the previous pick's end. Done.
• Why end time, not start time. The interval that ends earliest leaves the most room for future picks. This is the canonical exchange argument — swap any "different choice" with the earliest-ending one; you can still fit everything else.
• Canonical: LC 435 Non-overlapping Intervals, LC 452 Minimum Number of Arrows, LC 1029 Two City Scheduling (with a twist).

Shape B: interval covering (sort by start, extend right)

• Tell. "Cover the range [0, X] with minimum number of intervals", "minimum number of taps to water the garden", "find the smallest set of points hitting every interval".
• The rule. Sort by start. Iterate intervals; for the current uncovered position p, pick the interval (among those starting ≤ p) whose end is farthest right. Jump p to that end. Repeat.
• Different from Shape A. Shape A picks the earliest-finishing; Shape B picks the farthest-extending among feasible. Sorting key differs; selection rule differs; the exchange argument differs but is just as clean.
• Canonical: LC 1326 Minimum Number of Taps to Open to Water a Garden, LC 45 Jump Game II, LC 1024 Video Stitching.

Shape C: Huffman-flavour (always merge two smallest)

• Tell. The problem asks for an optimal cost where small things get combined into bigger things. "Merge piles", "build a prefix code minimising total bits", "connect ropes with minimum cost".
• The rule. Maintain a min-heap of remaining items. Repeatedly extract the two smallest, combine them (sum, merge, link), push the result back. Total cost is the sum of all intermediate combined-values.
• Why the smallest two. Items combined early get counted multiple times (their cost accumulates through every later combine they're part of). So you want the smallest items to be combined earliest, maximising the number of times the large items get counted (which is fewer combines).
• Canonical: Huffman codes (the optimal prefix coding), LC 1167 Minimum Cost to Connect Sticks.

Shape D: "take-all-you-can-while-it's-still-good"

• Tell. A one-pass sweep where at each step you have a local decision (buy / sell, refuel / skip, take / leave) and the goal is to maximise / minimise an accumulating quantity.
• The rule. Make the locally best move every time. If the price is going up, buy now and sell at the peak. If there's positive gas surplus, accept it; if negative, reset.
• Why it works. The future is decoupled — taking the good move now doesn't constrain the future moves (each step is independent of prior decisions). When this property holds, greedy is tight against any optimum.
• Canonical: LC 122 Best Time to Buy and Sell Stock II, LC 134 Gas Station, LC 860 Lemonade Change.

Shape E: the "regret" / "swap" reflex

• Tell. Each decision could be swapped with a future decision, and you need the "no swap improves the answer" property to hold. The greedy rule is "pick the locally best item AND verify that nothing later can replace it for the better".
• The rule. Often involves a heap to track the "weakest accepted" item. When a new item arrives that's better than the weakest accepted, swap them. Equivalent to "regret minimisation" in online algorithms.
• Why it's harder than Shape A. The exchange argument has two clauses, not one: local optimality AND no-swap-improves. Both must hold; missing either is a wrong greedy.
• Canonical: LC 1642 Furthest Building You Can Reach (regret on bricks vs ladders), LC 630 Course Schedule III (swap when overrun), LC 871 Minimum Number of Refueling Stops.

3 · Canonical example: Jump Game (LC 55)

Problem. Given an array nums where each nums[i] is the maximum jump length from index i, return whether you can reach the last index starting from index 0.

Input:  nums = [2, 3, 1, 1, 4]
Output: true
Explanation: jump 1 step from 0 to 1, then 3 steps from 1 to 4.

Input:  nums = [3, 2, 1, 0, 4]
Output: false
Explanation: every path lands on index 3, which has value 0.

Walk left to right tracking the farthest index reachable so far. At each index i, if i is beyond the current farthest, the answer is false — you can't even reach this index, let alone the end. Otherwise, update farthest with i + nums[i]. If the loop finishes, you reached the last index. The greedy rule is "always extend the reachable horizon as far as possible"; the exchange argument is that any reachable index is reachable via the farthest-horizon path, so no other strategy reaches further.

4 · Reference implementation

def can_jump(nums: list[int]) -> bool:
    max_reach = 0
    n = len(nums)
    for i in range(n):
        if i > max_reach:
            return False            # can't even reach this index
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= n - 1:
            return True             # last index already in range
    return True

5 · Variations

Most greedy problems boil down to picking the right sort key, then sweeping once. Six common variations:

5a · Interval scheduling, visually

Non-overlapping Intervals (LC 435) is the canonical "sort by end time, sweep" problem. Given 6 intervals on a timeline, the greedy picks the earliest-ending compatible interval, leaves the most room for what follows. Visualised against the wrong (sort-by-start) and the optimal (sort-by-end):

5b · Four greedy decision strategies

Greedy algorithms aren't one technique — they're a family of strategies that differ in how the "best local choice" is selected. Recognising which strategy a problem demands cuts the solution time dramatically.

6 · Five-problem progression

7 · Sister algorithms

Greedy is less a single algorithm than a family of proof techniques and combinatorial structures. Six of them are worth knowing by name — they're what you reach for when the basic "sort and sweep" doesn't quite close the problem, or when you need a deeper guarantee that the greedy is provably optimal.

• The exchange argument. The proof technique behind almost every "sort by X, take greedily" algorithm. Suppose OPT differs from GREEDY at the first step; swap OPT's first choice for GREEDY's; show the result is still valid and no worse. Recurse on the remaining suffix. The argument is short but the discipline of writing it cleanly is the senior-engineering signal. Every interval scheduling, activity selection, and job sequencing problem is proven by exchange.
• Matroid theory. The formal generalisation of "when does greedy give the optimum". A matroid is a pair (E, I) where E is a ground set and I is a family of "independent" subsets satisfying two axioms (hereditary: subset of independent is independent; exchange: if A and B are independent and |A| < |B|, some element of B can be added to A while keeping it independent). When the problem fits the matroid axioms, the greedy algorithm of "sort by weight, take if it keeps independence" is provably optimal; no exchange argument needed. The classical example is the graphic matroid: independent sets are forests, and Kruskal's MST falls out as a greedy on this matroid.
• Kruskal's MST. Greedy plus union-find. Sort edges by weight; iterate, adding each edge if its endpoints aren't already in the same component (use union-find for fast connectivity). The greedy is correct by the cut property: the minimum-weight edge crossing any cut belongs to some MST. Time O(E log E) dominated by the sort.
• Prim's MST. The same MST, built differently. Start at any vertex; maintain a heap of edges from "tree" vertices to "non-tree" vertices; repeatedly pop the cheapest such edge, add its non-tree endpoint to the tree. O(E log V) with a binary heap, O(E + V log V) with a Fibonacci heap. Prim is greedy + priority queue; Kruskal is greedy + union-find. Same problem, different data structure.
• Huffman coding. The canonical "always merge two smallest" greedy. Build a binary tree by repeatedly extracting the two minimum-frequency nodes from a heap, combining them into a new node whose frequency is the sum, pushing back. The leaf depths give an optimal prefix code (Shannon-optimal up to one bit). Used in gzip, JPEG, MP3, every compression codec that needs entropy coding.
• Hungarian algorithm. The matroid-style algorithm for the assignment problem (bipartite matching with weighted edges; find the minimum-cost perfect matching). Not "greedy" in the elementary sense (it uses augmenting paths and dual variables), but the matroid intersection structure means it's the natural generalisation of greedy MST to bipartite matching. Time O(n³) for n-on-n assignment.

7a · The exchange argument, traced through

Most candidates have heard "the greedy is correct by the exchange argument" without ever seeing the argument written down formally. Here it is for activity scheduling — the template generalises to every "sort by key, sweep" greedy you'll write.

Setup

Given a set of intervals, find the maximum-size subset of pairwise non-overlapping intervals. GREEDY: sort by end time, sweep, take each interval whose start is ≥ the previous accepted interval's end. Claim: GREEDY returns the same size as any optimal solution OPT.

The proof, step by step

1. Order both solutions by end time. Let GREEDY's picks be g₁, g₂, …, g_k in order of end time. Let OPT's picks be o₁, o₂, …, o_m in order of end time. We want to show k = m.
2. Compare g₁ and o₁. GREEDY picks g₁ as the interval with the earliest end time across all input intervals. So end(g₁) ≤ end(o₁). (Equality is possible if g₁ = o₁; that's fine.)
3. Show o₂ doesn't conflict with g₁. Since end(g₁) ≤ end(o₁) ≤ start(o₂), replacing o₁ with g₁ in OPT keeps the solution valid: o₂ still doesn't overlap with the new first pick.
4. Recurse on the suffix. After the swap, the modified OPT has g₁, o₂, o₃, …, o_m, the same size as the original OPT. Now repeat the argument: GREEDY's g₂ has end time ≤ any compatible interval, so we can swap o₂ → g₂, and so on.
5. Conclude. After k swaps, OPT has been transformed into g₁, g₂, …, g_k, o_(k+1), …, o_m. But after pick g_k, GREEDY found no further compatible interval: that means no compatible interval exists, so o_(k+1), …, o_m must be empty (otherwise GREEDY would have picked one of them). Therefore m = k.

What makes this template generalise

• The "GREEDY's choice is locally best" step. For activity scheduling, "locally best" means "smallest end time". For Huffman, it means "two smallest frequencies". For Kruskal, it means "minimum-weight edge that doesn't form a cycle". The proof shape is identical; only the local criterion changes.
• The "swap preserves feasibility" step. This is where most wrong greedies fall apart — the proposed swap creates an infeasibility (an overlap, a cycle, a precedence violation). If you can't prove this step cleanly, your greedy is probably wrong.
• The "swap doesn't decrease size / increase cost" step. For maximisation, the swap must not reduce the count. For minimisation, it must not increase the cost. This step is usually trivial once feasibility is established.

8 · Worked example: LC 435 Non-overlapping Intervals (classic activity scheduling)

Problem. Given a set of intervals, find the minimum number you need to remove so the remaining intervals don't overlap. Equivalently, find the maximum set of non-overlapping intervals; the answer is n − that.

Input:  [[1,2], [2,3], [3,4], [1,3]]
Output: 1
Explanation: removing [1,3] leaves [1,2], [2,3], [3,4] — all non-overlapping.

The rule and the proof

Sort by end time. Sweep left to right, maintaining the end time of the last accepted interval. For each new interval, accept it if its start is ≥ the previous end; otherwise skip (count it as a removal). This is the textbook activity-selection greedy.

Why end time, not start time. The interval that ends earliest leaves the most room for the rest. Suppose OPT keeps some interval other than the earliest-ending one. Swap OPT's choice for the earliest-ending interval. Since the swap-in ends earlier, every subsequent interval OPT could fit can still fit. So GREEDY's count is at least OPT's count — hence equal.

Go scaffold

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    if len(intervals) == 0 {
        return 0
    }
    // Sort by end time ascending
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    kept := 1                       // first interval is always kept
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end { // compatible with previous accepted
            kept++
            end = intervals[i][1]
        }
        // else: skip — implicitly counts as a removal
    }
    return len(intervals) - kept
}
// Time:  O(n log n) — sort dominates
// Space: O(1) extra (sort is in-place); O(log n) recursion stack

9 · Worked example: LC 134 Gas Station (clever single-pass greedy)

Problem. There are n gas stations on a circular route. Station i has gas[i] litres and the trip to station i+1 costs cost[i] litres. Return the starting station from which you can complete a full circuit, or -1 if none exists. Solution must be O(n) time and O(1) space.

Input:  gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: start at station 3 (gas 4), go to 4 (gas 5−1+4=8), to 0 (3−2+8=9),
             1 (6), 2 (4), back to 3 (2). Possible.

The two insights

• Insight 1: feasibility. If sum(gas) >= sum(cost), a starting station always exists. If sum(gas) < sum(cost), no station works. So compute totals first.
• Insight 2: the starting position. Sweep left to right tracking running surplus tank = gas[i] - cost[i] (cumulative). Every time tank goes negative, the current starting candidate is invalid, AND so is every station between the old start and this one (none of them could have survived if the cumulative starting from there is also negative; proof by sum splitting). Reset start to i + 1, reset tank to 0, continue.
• Why this works. Combined with insight 1, the start chosen after the last negative-reset must succeed (total is non-negative, so the suffix from that start is non-negative, and the wraparound completes the loop).

Go scaffold: single pass, no extra memory

func canCompleteCircuit(gas, cost []int) int {
    totalSurplus := 0
    tank := 0
    start := 0
    for i := 0; i < len(gas); i++ {
        diff := gas[i] - cost[i]
        totalSurplus += diff
        tank += diff
        if tank < 0 {
            // i is unreachable from current start; start over from i+1
            start = i + 1
            tank = 0
        }
    }
    if totalSurplus < 0 {
        return -1
    }
    return start
}
// Time:  O(n) — single pass
// Space: O(1)

The proof of why skipping ahead is safe

Suppose we start at station s and run out of gas at station j (i.e., cumulative surplus S(s..j) < 0 for the first time). For any s' ∈ (s, j], the cumulative surplus S(s..s'-1) ≥ 0 (otherwise we would have run out earlier). So S(s'..j) = S(s..j) - S(s..s'-1) < 0. Therefore no starting station in (s, j] works either — we can safely jump start to j + 1.

10 · Worked example: LC 502 IPO (HARD: greedy via two heaps)

Problem. You have an initial capital w and want to pick at most k projects to invest in. Project i requires capital capital[i] and yields profit profits[i]. Profit is added to your capital after completion; you can pick the next project from anything you can now afford. Return the maximum capital after k picks.

Input:  k = 2, w = 0
        profits = [1, 2, 3], capital = [0, 1, 1]
Output: 4
Explanation: with w=0, only project 0 affordable → pick it, w=1.
             Now project 1 or 2 affordable; pick higher (3) → w=4.

Why two heaps

• One min-heap on capital required. Projects you can't yet afford live here, sorted by capital ascending. As your wallet grows, you'll unlock more.
• One max-heap on profit. Projects you can afford live here. Always pick the most profitable one available.
• The dance. At each of the k rounds: move every project from the min-heap to the max-heap whose required capital is now ≤ w; pop the top of the max-heap; add its profit to w. Stop when the max-heap is empty (nothing affordable) or after k picks.

Go scaffold using container/heap

import "container/heap"

// Min-heap on (capital, profit)
type CapHeap [][2]int
func (h CapHeap) Len() int           { return len(h) }
func (h CapHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h CapHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *CapHeap) Push(x any)        { *h = append(*h, x.([2]int)) }
func (h *CapHeap) Pop() any          { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

// Max-heap on profit
type ProfHeap []int
func (h ProfHeap) Len() int           { return len(h) }
func (h ProfHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h ProfHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *ProfHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *ProfHeap) Pop() any          { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func findMaximizedCapital(k, w int, profits, capital []int) int {
    cap := &CapHeap{}
    for i, c := range capital {
        heap.Push(cap, [2]int{c, profits[i]})
    }
    prof := &ProfHeap{}

    for i := 0; i < k; i++ {
        // Promote everything we can now afford
        for cap.Len() > 0 && (*cap)[0][0] <= w {
            top := heap.Pop(cap).([2]int)
            heap.Push(prof, top[1])
        }
        if prof.Len() == 0 {
            break // nothing affordable — done early
        }
        // Greedy: take the highest-profit affordable project
        w += heap.Pop(prof).(int)
    }
    return w
}
// Time:  O((n + k) log n) — each project pushed/popped at most twice
// Space: O(n)

Why this is the senior-greedy archetype

• The greedy rule is non-obvious. "Take the highest-profit project you can currently afford." Proving it: any swap to a lower-profit affordable project decreases (or doesn't increase) your wallet, which can only decrease (or not increase) the set of future affordable projects, which can only decrease (or not increase) the future maximum. Pareto-dominated.
• The data-structure choice is half the answer. The two-heap structure is the right answer; one max-heap or one sorted list wouldn't capture the "unlocking" semantics cleanly. Interviewers want to see you reach for it.
• The amortised analysis matters. Each project is pushed at most once to each heap, popped at most once. Total work O((n + k) log n). Naive simulation per round is O(k · n); the heap version dominates when k is large.

10a · Greedy in production: where the pattern earns its keep

Greedy isn't a contest-only pattern. It's the bread and butter of several categories of real-world systems work. Recognising the production parallels is what helps the interview pattern click, and is what L5+ candidates pull out when asked "where would this matter in practice".

• Scheduling and dispatch. Earliest-deadline-first (EDF) is a provably optimal greedy for real-time scheduling — Linux's RT scheduler, every embedded RTOS, and most batch-job schedulers (LSF, Slurm) use EDF or close variants. Uber's dispatch matches riders to drivers with a greedy approximation of bipartite matching; the full Hungarian algorithm would be more accurate but isn't fast enough at fleet scale.
• Compression and coding. Huffman coding (greedy merge of lowest-frequency nodes) is the basis of every classical entropy coder: gzip, JPEG's DC component, the canonical Huffman tables in DEFLATE. Arithmetic coding gives better compression but Huffman is faster and patent-free, which is why it dominates in production despite the small efficiency loss.
• Memory allocation. Best-fit, first-fit, worst-fit are all greedy allocation strategies. jemalloc, tcmalloc, glibc's ptmalloc all use greedy size-class allocation: pick the smallest free chunk that fits, splitting if needed. The greedy choice (smallest fitting) is not optimal in the worst case (it can fragment), but is competitive in practice and an order of magnitude faster than backtracking allocators.
• Network routing. Border Gateway Protocol (BGP) picks routes greedily by attributes: local preference first, then AS path length, then origin, then MED. The choice isn't globally optimal but is locally Pareto-defensible and converges quickly across the internet's 70,000+ autonomous systems. OSPF and IS-IS use Dijkstra (greedy + priority queue) for intra-AS routing.
• Database query planning. Most cost-based optimisers (Postgres, MySQL, SQLite) use greedy join ordering for queries with more than ~10 tables — the full dynamic programming search space is O(3^n), too big for production. The greedy heuristic picks the next join with the lowest estimated cost; it produces sub-optimal plans on adversarial schemas but is fast enough to run on every query.
• Cache eviction. LRU is greedy in disguise — at every step, evict the entry whose access time is oldest. It's provably competitive with the optimal offline algorithm (Belady's) within a small constant factor. Memcached, Redis, the Linux page cache all use LRU or its approximations (clock, ARC, 2Q). LFU is greedy on frequency; SLRU partitions into protected and probationary segments.

11 · How to solve hard greedy problems, step-by-step

Hard greedy problems are mostly hard because the "wrong" greedy rules outnumber the "right" one. A discipline for working through them:

1. State the greedy choice in one sentence. "At each step, pick the X with minimum Y." If you can't fit the rule into one sentence, the rule is ambiguous and the proof will be harder than the code. Re-state until it's crisp. "Pick the interval whose end time is smallest among those compatible" — yes. "Pick the best-looking interval" — no, define "best".
2. Sketch a counter-example attempt. Spend 60 seconds trying to construct a small input (n = 3 to 5) where your greedy gives the wrong answer. If you find one quickly, your greedy is broken; switch to DP or revise the rule. If you can't find one after a minute, that's evidence (not proof) the rule is right. The act of attempting this is what catches the wrong-greedy bugs before they pass test 1 and fail test 17.
3. Draft an exchange argument. "Suppose OPT differs from GREEDY at the first step. Swap OPT's first choice for GREEDY's. The new solution is still valid (because the swap preserves constraints) and no worse (because GREEDY's choice was locally best by definition). Recurse on the suffix." Write this out, even informally. If the swap isn't valid (e.g., the swap creates an overlap, breaks a precedence constraint), the greedy is wrong.
4. Verify against brute force on small inputs. Run the greedy and a brute-force O(n!) or O(2^n) solution side by side for n = 5, 6, 7, 8 (10–15 random inputs). Compare answers. Any mismatch is the greedy being wrong; brute force is your reference truth. This catches the "I forgot a tiebreaker case" and "the proof has a gap" bugs that the eye misses.

12 · When greedy is NOT the answer

Greedy fails in predictable ways. Knowing the failure modes lets you rule it out fast and switch to DP without losing minutes to a wrong direction.

• Multiple dimensions of optimality (Pareto frontier). If the problem optimises two things at once (say, minimise cost AND minimise time, with the trade-off depending on context), greedy can't commit to a single local "best" because "best" is multi-dimensional. The Pareto frontier of non-dominated solutions has to be carried forward, which is DP (often with a 2D state). Weighted interval scheduling with profits is the textbook example: sorting by profit alone fails, sorting by end alone fails, the right answer is DP over sorted intervals.
• Local optima aren't global. Longest Increasing Subsequence is the classic. The greedy "always take the largest available" fails on [10, 1, 2, 3, 4] (greedy takes 10, length 1; LIS is 1,2,3,4, length 4). The greedy "always take the smallest available" also fails. There's no single-pass local rule; DP with patience-sorting (or binary search on the tails array) is the right tool. The signal: every greedy you propose loses on some adversarial input.
• You need to backtrack. Some problems require committing to a choice, exploring its consequences, then potentially un-committing. Sudoku, n-queens, partition problems with constraints: these all need backtracking, not greedy. The signal: the greedy rule depends on future information you don't yet have. Greedy without backtracking is fast but wrong; backtracking with good pruning is slower but correct.
• The optimisation is on a sum of correlated terms. Knapsack 0/1 is the textbook. Greedy by value-to-weight ratio works for fractional knapsack (the items are continuous) but fails for 0/1 because you can't take fractions, so the optimal subset might exclude the best ratio item to fit a worse-ratio combination. DP on (capacity, item index) is the right tool. The signal: items interact (taking one constrains another's space).
• Adversarial subsequences hidden in sorted data. Some problems look like "sort and pick the best k" but the picks interact through a hidden constraint. LC 1383 (Maximum Performance of a Team) is sort-by-efficiency-then-greedy-pick-by-speed, but with a heap to evict the worst speed when you exceed k. Pure sort-and-pick fails because the team's performance is min(efficiency) × sum(speed), where adding a low-efficiency engineer can hurt despite high speed.

13 · Common pitfalls

• Picking the wrong greedy rule. The big one. Interval scheduling sorted by start time looks plausible and is wrong; sorting by end time is correct. The first rule you think of is often not the one that works; sanity-check on a small adversarial example before committing.
• No proof or intuition before writing code. Greedy that passes the examples but fails on the hidden tests is the standard failure mode. Spend thirty seconds articulating why the choice is safe; if you can't, treat that as a signal.
• The "works on examples, fails on construction X" trap. Greedy is the pattern most likely to look right on the visible test cases and break on a carefully chosen counter-example. If you can't sketch the exchange argument, assume there's a counter-example you haven't found.
• Greedy on a problem that's actually DP. Weighted interval scheduling, 0/1 knapsack, longest increasing subsequence: these all have a greedy-looking shape and all need DP. The tell is usually that one choice's value depends on choices made later.
• Forgetting to handle ties. Two intervals with the same end time, two tasks with the same frequency, two items with the same ratio. The tiebreaker often matters; pick one consciously rather than relying on the sort being stable.
• Off-by-one in the sweep. Interval problems with closed vs half-open boundaries (does end == next.start count as overlap?) bite often. Decide the convention up front and write it in a comment.
• Picking the wrong sort key. Sorting intervals by start for activity scheduling looks fine and passes a few examples; the correct key is end. Sorting jobs by profit looks fine for weighted job scheduling; the correct approach is DP. Sorting items by value looks fine for knapsack; the correct key for fractional knapsack is value-to-weight ratio, and for 0/1 it's not greedy at all. The sort key is the single most error-prone choice in the entire pattern. Sanity-check by trying the "obvious" wrong key on a small adversarial input.
• Missing the "no-swap" condition. The exchange argument has two clauses: (1) the greedy's choice is locally best, (2) no future swap can improve on the greedy's choice retroactively. Most beginners verify clause 1 and forget clause 2. The regret/swap family of problems (LC 1642 Furthest Building, LC 871 Refueling Stops) is where clause 2 is the whole game; missing it produces a greedy that's locally optimal but globally wrong.
• Assuming greedy on a problem that needs DP. The temptation is strong: greedy is shorter, faster, and feels elegant. But weighted interval scheduling, 0/1 knapsack, LIS, edit distance, all coin-change variations: these all have greedy-shaped surfaces and need DP underneath. The tell: if removing the "all weights are 1" or "all items same size" assumption breaks your greedy, you were doing DP all along and didn't notice.
• Off-by-one on interval endpoints. Is [1, 3] closed or half-open? Does it overlap with [3, 5]? The conventions vary across problems (LC 56 Merge Intervals uses closed-closed; LC 252 Meeting Rooms treats end == start as non-overlap). Always decide and comment, and ensure your comparison operator matches: intervals[i][0] >= end for half-open, intervals[i][0] > end for closed-closed.
• Heap-based greedy with wrong comparator. Go's container/heap requires you to implement Less correctly: for a max-heap on profit, Less(i, j) = h[i] > h[j] (inverted). For a min-heap, Less(i, j) = h[i] < h[j]. A subtle flip here produces a greedy that always picks the worst-instead-of-best, usually visible because the answer is way off, but sometimes only off by one on certain inputs.

14 · What to say in the interview

1. "This looks greedy — let me try to articulate the rule." Name the pattern out loud, then state the proposed local choice in one sentence.
2. Always articulate the exchange argument. "If my greedy choice weren't optimal, take an optimal solution that disagrees with mine at the first step, swap in my choice, and show the result is no worse." This sentence, said out loud, is what separates a confident greedy answer from a guess.
3. Sanity-check on a small adversarial input. Before coding, sketch a case designed to break the rule. If you can't construct one, that's evidence (not proof) the rule is right.
4. State that DP is the fallback. "If the exchange argument doesn't go through, I'd reach for DP — the recurrence is usually easy to write once you have the state." Signals that you know greedy isn't always available.
5. Complexity is usually O(n log n). The sort dominates; the sweep is linear. Say both pieces.
6. Edge cases to mention. Empty input, single element, all-equal elements, ties on the sort key, inputs where the greedy choice is forced (only one option).

15 · Where this gets asked

16 · Try it yourself

Jump Game · LC 55

The one-pass max-reach pattern. Hint: track max_reach as you sweep. If i > max_reach at any point, return false. Otherwise extend max_reach = max(max_reach, i + nums[i]).

Non-overlapping Intervals · LC 435

Interval scheduling: the canonical greedy proof. Hint: sort by END time, not start. Then greedily keep intervals whose start >= previous end. Why end time? Because picking the earliest-ending interval leaves the most room for everything else.

Task Scheduler · LC 621

Heap + cooldown: the operational-research flavour. Hint: count frequencies, push into a max-heap, schedule top-k each cycle with a cooldown queue. Alternatively, the closed-form (max_count - 1) * (n + 1) + tie_count works if you can prove the bound.

Partition Labels · LC 763

One-pass with a precomputed "last index" map. Hint: first pass, record last[ch] = i for every character. Second pass, extend the partition end to max(end, last[s[i]]); cut whenever i == end.

Stretch: Candy · LC 135

Two-pass greedy where neither direction alone suffices. Hint: left-to-right pass, if r[i] > r[i-1] then c[i] = c[i-1] + 1. Right-to-left pass, if r[i] > r[i+1] then c[i] = max(c[i], c[i+1] + 1). Sum.

Further reading

• Kleinberg & Tardos — Chapter 4. The classic greedy chapter. Interval scheduling, scheduling to minimise lateness, Huffman codes, and the exchange-argument template, done carefully and with proofs. The single best resource for this pattern.
• Erickson — Algorithms, Chapter 4. Free online (jeffe.cs.illinois.edu). Sharper, shorter treatment with good adversarial examples for why naive greedy rules fail.
• CLRS — Chapter 16. Includes the matroid section for the theoretically curious. Skim unless you want the formal exchange-property statement.
• Adjacent: Dynamic programming. The fallback when greedy fails. Knowing both well lets you choose deliberately rather than guess.
• Adjacent: Sorting. Most greedy solutions start with a sort. Picking the right key is half the problem.
• Semicolony: Sorting visualizer. Useful for building intuition about how a chosen sort key reshapes the input.