Greedy
01 / The shared mechanism
At every step, take the locally optimal commit — and prove that the commit is never undone later. No backtracking, no DP table: either an exchange argument says swapping any greedy choice cannot improve the answer, or a stays-ahead argument shows greedy keeps a lead at every prefix. Three classic sub-patterns turn that idea into algorithms: sort-and-take on intervals, scan-and-reach on arrays, and a single-pass "reset on failure" on cumulative inputs.
01 / The one-sentence essence
Sort intervals by end, then walk through and take each one whose start clears the last taken end. The exchange argument proves earliest-end is always a safe commit — anything else can only do as well or worse.
Problemmax non-overlapping intervalsInput[1,3] [2,5] [3,6] [5,9] [8,12]
Input has 5 intervals in their given order. The greedy idea: sort by end, then walk through and take each one whose start clears the last taken end.
step
0 / 12
taken
—
lastEnd
−∞
0 / 12
02 / The pattern signature
# sort by end — not startintervals.sort(key=lambda iv: iv.e)result ← []; lastEnd ← −∞for iv in intervals:if iv.s ≥ lastEnd:result.push(iv) # take itlastEnd ← iv.eelse:# skip — would clash with the last taken interval# |result| is the maximum non-overlapping count
03 / When to recognize this pattern
"maximum non-overlapping intervals"
The textbook trigger. Meeting rooms, classroom bookings, activity selection — anything where the answer is the largest set you can pick without overlap. Sort by end and take greedily; you're done.
"minimum to remove to make non-overlapping"
LC 435's phrasing. It's the same problem in disguise: max kept = max non-overlap, so removed =
N − kept. The greedy sort-by-end gives both for free."minimum darts / arrows to burst balloons"
LC 452. Each balloon is a closed interval and an arrow at x bursts every balloon covering x. The answer is the minimum number of disjoint groups — equivalently, the maximum non-overlapping selection counted from the other side.
"weighted interval scheduling"
Sounds the same but isn't — once each interval has a profit and you want maximum total value, the greedy choice can be wrong. That problem becomes DP over intervals sorted by end with predecessor lookup (LC 1235).
04 / Common pitfalls
i.
Sorting by start instead of end.
The most common bug. Sorting by start works on simple disjoint inputs, but fails the moment a long interval appears early — committing to it blocks several shorter ones that all could have fit. Sort by end and the locally cheapest commit is also the globally safest one.
ii.
Strict
> vs non-strict ≥ on the boundary.Does
[1, 5] followed by [5, 8] count as overlapping? For closed intervals (LC 452 balloons) endpoints touching do overlap — use strict >. For half-open intervals (calendar events ending at 10:00 don't clash with one starting at 10:00) use ≥. Same skeleton, opposite comparator.iii.
Confusing this with merge intervals.
Merge intervals sorts by start and collapses overlaps into output ranges. Interval scheduling sorts by end and counts how many fit without overlap. They look alike but answer different questions: union vs maximum disjoint set.
05 / Go practice — on LeetCode
Four problems, ordered roughly by difficulty. The hard one — LC 1235 — is the cautionary tale: add weights and the greedy choice breaks, so it's actually DP.
— / When to use which
interval scheduling
Use when the input is a list of intervals and the question is "how many non-overlapping picks?" Sort by end, then take each interval whose start clears the last taken end. The exchange argument proves earliest-end is always safe.
sort by end · LC 435 · LC 452
jump game
Use when each element bounds how far you can move from it. Sweep left to right, tracking the farthest index reachable so far; if the sweep ever passes that frontier, the end is unreachable.
track farthest · LC 55 · LC 45
gas station
Use when a cumulative quantity must stay non-negative through a circular or linear walk. Reset the start the moment the running total dips below zero — any failing segment cannot be a valid starting prefix.
reset on failure · LC 134 · LC 53