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.
Pick a sub-pattern above. Each is independently linkable — start where the problem statement points.
↑ choose one— / 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