Greedy

The lightbulb moment: the Greedy Buffet

Imagine a buffet dinner where you want to eat the maximum number of dishes, but each dish takes a different amount of time. You only have 2 hours. A greedy person grabs the dish that finishes fastest every single time. Why? Because finishing a fast dish wastes the least time, leaving maximum opportunity for more dishes afterward. That's the entire greedy insight: choose what ends earliest (or costs least), so you leave maximum room for the future.

The danger: a greedy strategy only works when the "locally best" choice never blocks a globally better outcome. Like the buffet — it doesn't work if some dishes can only be eaten in a specific order (dependencies break greedy). Proving "it's safe to be greedy" is the whole skill.

🧠 Coin change trap: With coins 4, making 6 cents: greedy picks 4+1+1 = 3 coins. Optimal is 3+3 = 2 coins. Greedy failed because taking 4 blocked using two 3s. Same structure, different numbers — greedy can break. This is why you always test with a small example before trusting it!

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?".

Complexity at a glance

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

import java.util.Arrays;

public class MaxMeetings {
    public static int maxMeetings(int[][] intervals) {
        // Sort by END time — the greedy insight
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 0;
        int freeAt = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] >= freeAt) {   // doesn't overlap last pick
                count++;
                freeAt = interval[1];
            }
        }
        return count;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

int maxMeetings(vector<pair<int,int>>& intervals) {
    // Sort by END time — the greedy insight
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b){ return a.second < b.second; });
    int count = 0, freeAt = INT_MIN;
    for (auto& [start, end] : intervals) {
        if (start >= freeAt) {    // doesn't overlap last pick
            count++;
            freeAt = 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

public boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;       // gap we can never cross
        reach = Math.max(reach, i + nums[i]); // extend frontier
    }
    return true;
}

bool canJump(vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) return false;                    // unreachable gap
        reach = max(reach, i + nums[i]);                // extend 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.

Think it through

The chapter's whole discipline is "state the rule, then argue it's safe." Practice that on a problem where the safety argument — why you can skip a whole failed prefix — is the entire trick. Think before revealing.

Check yourself

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.