Greedy

The pattern

A greedy algorithm builds the solution one step at a time, always taking the choice that looks best right now, never revisiting. No recursion tree, no memo table — usually just a sort and a single pass, O(n log n).

That simplicity is exactly the danger: greedy is only correct when the problem has the right structure, and proving (or at least arguing) that structure is what separates a guess from an answer. The contrast to internalize:

• Greedy works → local best never blocks global best (taking it leaves the remaining subproblem no worse).
• DP needed → today's choice changes what's possible tomorrow in ways you must compare (overlapping subproblems, decisions interact).

Coin change is the canonical fence: with coins 25, greedy (largest coin first) is optimal. With coins 4 and target 6, greedy gives 4+1+1 (three coins); optimal is 3+3 (two). Same problem, different data, greedy breaks — which is why "would greedy work here?" must be followed by "why?".

Watch a correct greedy run

The classic where greedy is provably right: fit the most meetings into one room by always taking the one that ends earliest. Watch the rule accept and reject in one pass — then try your own meeting list and predict each verdict before it lands.

The argument that makes it correct

The standard tool is the exchange argument: take any optimal solution that disagrees with greedy's first choice, show you can swap in greedy's choice without making it worse — therefore some optimal solution agrees with greedy; repeat for every step.

See it on the flagship problem — interval scheduling (max number of non-overlapping meetings): greedy = always pick the meeting that ends earliest.

Why earliest end? Suppose an optimal solution's first meeting ends at time t, while greedy's ends at t' ≤ t. Swap greedy's in: it ends no later, so everything that fit after t still fits after t'. Still optimal, now agreeing with greedy. ∎

def max_meetings(intervals):
    intervals.sort(key=lambda iv: iv[1])    # by END time — the insight
    count, free_at = 0, float("-inf")
    for start, end in intervals:
        if start >= free_at:                # doesn't overlap the last pick
            count += 1
            free_at = end
    return count

Sorting by start time or by duration both fail (build a 3-interval counterexample for each — genuinely worth doing once). The pattern of the whole genre: greedy = sort by the right key + one linear pass; the interview is finding the right key.

The classics, by family

Intervals (the biggest family — see heaps & intervals for the heap-flavored ones):

• Max non-overlapping meetings → sort by end (above).
• Min arrows to burst balloons / remove min intervals to de-overlap → same idea in costume.
• Meeting rooms needed → different question (max overlap), different tool: heap of end-times or a sweep line.

Reachability / jumps:

def can_jump(nums):                  # Jump Game: each value = max jump length
    reach = 0
    for i, step in enumerate(nums):
        if i > reach: return False   # gap we can never cross
        reach = max(reach, i + step) # greedily extend the frontier
    return True

Track the best frontier; never simulate individual paths. (Jump Game II — minimum jumps — is the same frontier idea with level counting, BFS in disguise.)

Circular residue: Gas Station — if total gas ≥ total cost a solution exists; restart the candidate start whenever the running tank goes negative. One pass, and the "why is restarting safe?" follow-up is an exchange argument in miniature.

Two-pointer greedy: assign cookies to children, boats to people — sort + two pointers, matching greedily from the ends.

Structural greedy: Kruskal's MST — sort edges, take unless it forms a cycle (union-find does the check); Huffman coding — repeatedly merge the two rarest symbols (heap). Both have classic exchange proofs.

How to spot greedy in the wild

Signals it might be greedy: "maximum number of…", "minimum number of…", one resource consumed in order (time, fuel, capacity), and — strongest — sorting by something makes the problem look one-dimensional.

Signals it's not: "count the ways" (DP), "print all" (backtracking), choices with delayed consequences you can't rank locally (knapsack: value and weight pull differently — that's DP).

Honest interview protocol: state the greedy rule → try to break it with a small adversarial example (30 seconds, out loud) → if it survives, sketch the exchange argument → code. Trying to break your own idea is itself a senior signal; greedy answers without an argument are how candidates fail problems they "knew."

Production perspective

• Schedulers everywhere are greedy: OS shortest-job-first, load balancers picking least-loaded (scalability), Kubernetes bin-packing pods — greedy with heuristics, accepting near-optimal.
• Huffman is inside every zip/JPEG; Dijkstra (graphs) is greedy with a heap; interval scheduling is calendar/booking logic.
• The engineering meta-lesson: production often chooses greedy knowingly — optimal is NP-hard, greedy is fast and 95% as good. "Greedy approximation" is a respectable phrase in design reviews (HLD trade-offs).

Common mistakes

• No counterexample attempt — the #1 failure. Thirty seconds of trying to break your rule catches most wrong greedies before the interviewer does.
• Sorting by the plausible-but-wrong key — start time instead of end time; value instead of value/weight ratio; duration instead of deadline. The key is the problem.
• Greedy on knapsack — 0/1 knapsack by ratio fails (it's DP); fractional knapsack by ratio is correct. Know which is which.
• Mutating the wrong frontier — in reach-style problems, update the best-known frontier, don't branch into paths.
• Calling it greedy without saying why it's safe — even one sentence ("ending earlier can never block more meetings") converts a guess into an answer.

Interview perspective

Practice

1. Break things (the core skill): for interval scheduling, construct counterexamples where sort-by-start and sort-by-duration each fail. Three intervals suffice for each.
2. The canon: max meetings (memory); Jump Game I & II; Gas Station; assign cookies (two-pointer greedy); non-overlapping intervals (min removals).
3. Exchange reps: write the 3-sentence exchange argument for "min platforms/meeting rooms uses a heap of end times" and for Kruskal. Out loud. Interviewers ask "why" more than "how".
4. Capstone: task scheduler with cooldown (LeetCode 621) — greedy on the most frequent task with a formula, or simulate with a heap. Do both; compare.

That closes the core Level 3 patterns. Apply them at scale in the problem bank and the Blind 75.

Practice — climb the ladder

Greedy is only correct when a local choice provably never blocks a better future. Practice writing that one-sentence proof before coding.