Common Greedy Interview Patterns

Pattern recognition should suggest a candidate greedy rule, not replace the proof. When you see intervals, deadlines, reachability, limited resources, or string feasibility, map the problem to a known template and then verify the greedy-choice property for the exact objective.

The best candidates explain both the signal and the invariant. Signal tells you which template to try. Invariant tells you why the scan remains correct after every choice.

Use the sort-by-end template when you must maximize the number of non-overlapping intervals, remove the fewest overlaps, or place the minimum number of resources over interval ranges. The signal is that choosing an interval or arrow creates a right boundary that future items must respect. Sorting by end time or right endpoint makes the earliest finishing compatible choice available first.

The invariant is that the chosen boundary is as far left as possible among equally good partial solutions. For interval scheduling, earlier end leaves more room. For arrows bursting balloons, placing an arrow at the current smallest end keeps it inside the current overlapping group while maximizing the chance it also hits later balloons in that group.

Use earliest-deadline scheduling when tasks, events, or courses have deadlines and each accepted item consumes time. The usual signal is a feasibility condition like total time must not exceed the current deadline. Sometimes the greedy rule is to process by increasing deadline and drop the longest accepted task when feasibility breaks, because removing the longest task frees the most time with one removal.

Use farthest-reach arrays when each position expands a reachable frontier, as in Jump Game and Jump Game II. The signal is that among all choices available in the current window, only the farthest future boundary matters. Shorter reaches are dominated because they cannot unlock anything that the farther reach cannot also reach.

Use a heap when the greedy algorithm needs to revise a previous choice while scanning in a meaningful order. The scan order often comes from time, deadline, height, capital, or position. The heap stores the best candidate to add next or the worst accepted candidate to remove if a constraint becomes violated.

Common signals include choose the largest profit among currently affordable projects, use ladders on the biggest climbs seen so far, or keep accepted courses but discard the longest duration when deadlines fail. The invariant is not that the algorithm never changes its mind. It is that after each prefix, the heap represents the best feasible set for that prefix under the chosen resource constraint.

Use last-occurrence templates when a string decision must ensure that required characters can still appear later. Partition Labels expands the current segment to the farthest last occurrence of any character inside it; a cut is safe only when the scan reaches that farthest boundary. Remove Duplicate Letters chooses a small character only after confirming that popped characters occur again later.

The signal is future availability. A locally smaller character or earlier cut is unsafe if it loses the final copy of something required. The invariant tracks whether every deferred character can still be recovered. Once the invariant says the future remains feasible, the greedy choice can be locked in.