Greedy — A Masterclass in Thinking

This is long on purpose — it's a course, not a cheat sheet (though the cheat sheets are at the bottom). Read it like this:

Front-loaded toward thinking & proving, back-loaded with patterns & reference. Jump around with the rail on the right (or the "Sections" button on mobile), but the first read should be in order.

01 · What greedy actually is#

Forget "makes the locally optimal choice at each step" for a minute. That's the description of the code, not the reason it's allowed. Here's the feeling:

Everything else — the sort key, the heap, the one-pass loop — is just machinery for exposing which move is regret-free. Once you believe greedy is "commit only to provably-safe moves," the mystique inverts: the code was never the hard part. The hard part is the licence to commit. DP earns its answer by comparing every future; greedy earns its answer by proving it never needs to.

The two mental models, ranked by usefulness#

The two properties that make greedy legal#

Now we can earn the textbook words. Greedy is correct when a problem has both:

• Greedy-choice property — there's always a locally-optimal move that is part of some globally-optimal solution. (This is "the no-regret move exists." It's the property you must prove, usually by an exchange argument.)
• Optimal substructure — after committing to that move, what remains is a smaller instance of the same problem, and an optimal solution to the whole contains an optimal solution to the rest. (This is what lets you repeat.)

DP needs optimal substructure too — but DP lacks the greedy-choice property, so it must try every first move and compare. The single question that separates them: is there one first move I can commit to blindly, or must I compare futures? Commit → greedy. Compare → DP.

02 · Why humans struggle with greedy#

You are not bad at greedy. You're missing the two things editorials delete: the search for the choice and the proof that it's safe. What's left — the sort and the loop — looks so simple that your own struggle feels like stupidity. It isn't. Let's name the specific gaps.

03 · When to suspect greedy — and when to run#

Greedy and DP answer the same kinds of questions (optimize / count / feasibility over choices), which is why they're confusable. The difference is never in the question — it's in whether a single first move is safe to commit to. Run this decision flow:

The confusion table — greedy vs its look-alikes#

04 · The engine: candidates → counterexamples → proof#

DP's engine is "recursion, then cache." Greedy's engine is different in spirit: propose, attack, prove. You are a prosecutor trying to convict a greedy rule — and only the one you fail to break gets to stand trial by proof.

A full worked derivation: Activity Selection#

Problem: you have n activities, each with a start and finish time. You can do one at a time; two activities conflict if they overlap. Select the maximum number of non-overlapping activities.

Step 1–2 · Objective & brute force#

Objective: maximize the count of chosen non-overlapping activities. Ground-truth brute force: try every subset, keep the largest that has no overlaps — O(2ⁿ). Useless for big n, but priceless as an oracle to test candidates against (Step 4, and again in debugging).

Step 3 · Brainstorm candidate choices#

What could the "obvious" first pick be? Don't commit — list them. Each is a hypothesis:

All three are reasonable. That's the trap — reasonableness is not correctness. Now we hunt counterexamples.

Step 4 · Attack each candidate — the interactive part#

Below is one fixed set of six activities. Pick a sort key and step the greedy sweep: it keeps an activity if it starts at/after the last kept finish, else rejects it. Watch two of the three "reasonable" rules select fewer than the optimum of 4. Losing on purpose is the point.

Earliest finish (C) is the lone survivor — it hits 4. The counterexamples didn't just crown it; they told us why: what matters isn't when an activity starts or how long it is, but how soon it frees the resource. Finishing early is the property that never wastes the future.

Step 5–6 · Take the survivor & prove it (staying-ahead)#

Candidate: repeatedly pick the compatible activity with the earliest finish time. Here's the proof, intuitively, then we'll formalize it in Part IV. Number greedy's picks g₁, g₂, … by finish time, and any other solution's picks o₁, o₂, … likewise.

Step 7 · Implement — five lines, now trusted#

// Activity Selection: max non-overlapping activities.
// Each row: {start, end}. Half-open intervals: [s, e).
int maxActivities(int[][] acts) {
    // The whole strategy: process by earliest finish time.
    Arrays.sort(acts, (a, b) -> Integer.compare(a[1], b[1]));  // sort by END
    int count = 0, lastEnd = Integer.MIN_VALUE;
    for (int[] a : acts) {
        if (a[0] >= lastEnd) {   // compatible: starts at/after last finish
            count++;             // COMMIT — no regret (proven safe)
            lastEnd = a[1];      // resource now free at a[1]
        }
    }
    return count;
}

05 · Inventing the choice — the questions that surface it#

Step 3 ("brainstorm candidates") feels like the creative leap, but it's mostly mechanical if you interrogate the problem with the right questions. Ask these, in order, out loud:

06 · The proof toolkit#

Technique 1 · The exchange argument, visualized#

This is the workhorse. The move: assume an optimal solution OPT disagrees with greedy at the first choice. Swap greedy's choice into OPT. Show the swap keeps OPT valid and no worse. Since one swap removes one disagreement without cost, repeating turns OPT into greedy — so greedy is optimal too. Step through it on activity selection:

The engine of the whole proof is one line: greedy's choice finishes no later than OPT's, so wherever OPT's choice fit, greedy's fits too — the swap can't create a conflict, and it can't reduce the count. That "no later, so it fits anywhere yours did" reasoning is the shape of nearly every greedy exchange proof. Memorize the shape, not the problem.

Technique 2 · Staying-ahead ("greedy is never behind")#

Instead of transforming OPT, you race against it. Define a measure of "how well positioned" a partial solution is after k steps, then prove by induction that greedy's measure is always at least as good as any other's. If greedy is never behind at any step, it can't finish worse.

Special case · the cut property (why MST greedies work)#

For Minimum Spanning Tree (Kruskal / Prim), the greedy-choice property has a famous name: the cut property.

Kruskal applies this by always adding the globally-cheapest edge that doesn't form a cycle (it's the min crossing edge for the cut separating the two components it joins). Prim applies it by always adding the cheapest edge leaving the tree built so far. Same cut property, two orderings.

The deep "why" · matroids (optional, but it demystifies everything)#

You don't need this to solve problems, but it answers "why does sort-and-take work for MST and scheduling but not knapsack?" A matroid is a structure with an "exchange property": if you have two independent sets and one is bigger, you can always move an element from the bigger into the smaller and stay independent. Whenever your problem's feasible solutions form a matroid, the greedy "sort by weight, take if still feasible" is provably optimal. MST's forests form a matroid → Kruskal works. Knapsack's under-capacity sets do not form a matroid → greedy fails, DP needed. The exchange property of matroids is literally the exchange argument, generalized.

07 · Why greedy fails — and how to catch it early#

Knowing where greedy breaks is as valuable as knowing where it works — it's what stops you from confidently shipping a wrong five-liner. Every greedy failure has the same signature: a locally-worse choice can win globally. Learn to smell it.

Failure gallery#

08 · Sorting — why greedy almost always starts here#

Sorting is greedy's default opening because it does one magical thing: it puts the dominant choice first at every step, so a single left-to-right pass can commit to moves in the right order. If your greedy choice is "the extreme one" (earliest, cheapest, best ratio), sorting by that key means "the front of the list is always the move to consider next."

09 · Data structures — re-revealing the best move#

A one-time sort works when the "best move" order is fixed up front. But sometimes the best move changes as you commit (the two smallest ropes change after each merge; the nearest node changes as you settle others). Then you need a structure that re-surfaces the current best in O(log n).

10 · The families#

Arrays.sort(iv, (a, b) -> Integer.compare(a[1], b[1])); // by END
int taken = 0, lastEnd = Integer.MIN_VALUE;
for (int[] x : iv)
    if (x[0] >= lastEnd) { taken++; lastEnd = x[1]; }   // keep & advance
// "min removals" = n - taken. "min arrows" = same count, using x[0] > lastEnd (strict).

Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));   // by START
PriorityQueue<Integer> endTimes = new PriorityQueue<>();   // min-heap of end times
for (int[] m : iv) {
    if (!endTimes.isEmpty() && endTimes.peek() <= m[0]) endTimes.poll();          // a room freed up; reuse it
    endTimes.add(m[1]);           // occupy a room until m[1]
}
return endTimes.size();           // peak concurrency = rooms needed

int farthest = 0;
for (int i = 0; i < nums.length; i++) {
    if (i> farthest) return false;               // fell off the frontier
    farthest = Math.max(farthest, i + nums[i]);   // extend reach
}
return true;

int total = 0, tank = 0, start = 0;
for (int i = 0; i < n; i++) {
    int gain = gas[i] - cost[i];
    total += gain;
    tank  += gain;
    if (tank < 0) { start = i + 1; tank = 0; }  // this prefix can't be a valid start
}
return total >= 0 ? start : -1;                 // solvable iff total gain >= 0

int[] c = new int[n];
Arrays.fill(c, 1);
for (int i = 1; i < n; i++)                    // left→right: respect left neighbor
    if (rating[i] > rating[i-1]) c[i] = c[i-1] + 1;
for (int i = n - 2; i >= 0; i--)               // right→left: respect right neighbor
    if (rating[i] > rating[i+1]) c[i] = Math.max(c[i], c[i+1] + 1);
int total = 0; for (int x : c) total += x;
return total;

PriorityQueue<Integer> pq = new PriorityQueue<>();   // min-heap
for (int len : ropes) pq.add(len);
int cost = 0;
while (pq.size() > 1) {
    int a = pq.poll(), b = pq.poll();  // the two smallest — the safe merge
    cost += a + b;
    pq.add(a + b);                     // re-insert the merged rope
}
return cost;

Deque<Character> st = new ArrayDeque<>();
for (char d : num.toCharArray()) {
    while (k > 0 && !st.isEmpty() && st.peek() > d) {
        st.pop(); k--;             // a bigger earlier digit hurts — drop it
    }
    st.push(d);
}
while (k-- > 0) st.pop();           // still must remove? drop from the end
// build result from the stack bottom-up, strip leading zeros

Arrays.sort(jobs, (a, b) -> Integer.compare(b.profit, a.profit)); // profit desc
boolean[] slot = new boolean[maxDeadline + 1];
int profit = 0;
for (Job j : jobs)
    for (int t = j.deadline; t >= 1; t--)   // latest free slot (DSU makes this O(α))
if (!slot[t]) { slot[t] = true; profit += j.profit; break; }
return profit;

Arrays.sort(items, (a, b) -> Double.compare((double) b.value / b.weight, (double) a.value / a.weight)); // ratio desc
double value = 0; int cap = W;
for (Item it : items) {
    if (cap == 0) break;
    int take = Math.min(it.weight, cap);          // full item, or a fraction
    value += (double) it.value * take / it.weight;
    cap   -= take;
}
return value;

Arrays.sort(edges, (a, b) -> Integer.compare(a.w, b.w)); // cheapest first
DSU dsu = new DSU(n);
int cost = 0, used = 0;
for (Edge e : edges) {
    if (dsu.union(e.u, e.v)) {   // union returns false if it would form a cycle
        cost += e.w;
        if (++used == n - 1) break;   // spanning tree complete
    }
}
return cost;

11 · Java templates#

The skeletons every greedy reuses. Fill in the comparator and the "is this move safe here?" check — the structure never changes.

Custom comparators & sorting objects#

// Sort intervals by end time (activity selection):
Arrays.sort(iv, (a, b) -> Integer.compare(a[1], b[1]));

// Multi-key: by end asc, tie-break by start desc:
Arrays.sort(iv, (a, b) -> a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]);
// NOTE: use Integer.compare, not a-b, when values can overflow int subtraction.

// Pairwise "which should come first" (Largest Number):
String[] s = ...;
Arrays.sort(s, (x, y) -> (y + x).compareTo(x + y));  // x before y iff x+y is larger

// Objects by a derived ratio (fractional knapsack), descending:
items.sort((a, b) -> Double.compare((double) b.value / b.weight, (double) a.value / a.weight));

Priority queue (heap) — dynamic best move#

PriorityQueue<Integer> min = new PriorityQueue<>();               // min-heap
PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());

// heap of objects by a field (e.g. by end time):
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

// idiom: repeatedly take the extreme, transform, re-insert
while (pq.size() > 1) {
    int a = min.poll(), b = min.poll();
    min.add(a + b);   // Huffman-style merge
}

TreeMap / TreeSet — nearest available#

TreeSet<Integer> set = new TreeSet<>();
set.add(x);
Integer ge = set.ceiling(k);   // smallest element >= k  (nearest available slot up)
Integer le = set.floor(k);     // largest element  <= k  (nearest available slot down)

TreeMap<Integer,Integer> map = new TreeMap<>();   // sorted multiset / booking counts
map.merge(start, 1, Integer::sum);
map.merge(end, -1, Integer::sum);                // ±1 sweep; iterate keys in order

Union-Find (DSU) — merge sets, reject cycles#

class DSU {
    int[] p, r;
    DSU(int n) { p = new int[n]; r = new int[n]; for (int i = 0; i < n; i++) p[i] = i; }
    int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }   // path compression
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;               // already connected → would cycle
        if (r[ra] < r[rb]) { int t = ra; ra = rb; rb = t; }
        p[rb] = ra; if (r[ra] == r[rb]) r[ra]++;  // union by rank
        return true;
    }
}

Interval sweep (event sorting) — peak concurrency#

// Turn each interval into two events; sort; track a running counter's max.
int[][] ev = new int[2 * n][2];
for (int i = 0; i < n; i++) { ev[2*i] = new int[]{iv[i][0], +1}; ev[2*i+1] = new int[]{iv[i][1], -1}; }
// tie rule: process -1 (end) before +1 (start) at equal time if touching is allowed to share
Arrays.sort(ev, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int cur = 0, peak = 0;
for (int[] e : ev) { cur += e[1]; peak = Math.max(peak, cur); }
return peak;

12 · Debugging greedy — the stress test is your proof substitute#

Greedy bugs are silent: you get a plausible number that's just wrong on some input you didn't try. You can't "read a table" like DP. Your single most powerful tool is the stress test: pit your greedy against a brute-force oracle on thousands of random small inputs. It's how contest programmers trust a greedy they can't quickly prove.

// Stress test: greedy vs brute force on random tiny inputs.
Random rng = new Random(42);
for (int t = 0; t < 100_000; t++) {
    int[][] input = randomSmallCase(rng);   // small n so brute force is feasible
    int g = greedy(input);
    int b = bruteForce(input);              // honest exponential ground truth
    if (g != b) {
        System.out.println("COUNTEREXAMPLE:");
        System.out.println(Arrays.deepToString(input));
        System.out.println("greedy=" + g + " brute=" + b);
        break;   // now you have a minimal case to study — the tell for WHY greedy is wrong
    }
}

13 · Interview thinking — the monologue#

Here's the internal narration of someone solving a greedy problem cold. Notice they never "recall the trick" — they run the engine out loud, and they earn trust before coding. Steal this script.

14 · The problem roadmap#

Order matters. Each tier adds one idea on top of the last. Don't skip — the "why next" is the point. Finish a tier before the next.

Tier 0 · Feel the safe move easy#

1. Assign Cookies↗ Sort both sides, match greedily — the gentlest "sort then two-pointer" safe move.
2. Maximum Units on a Truck↗ Sort by units desc, take greedily. First "which key?" decision.
3. Lemonade Change↗ Give the largest bills first; a tiny exchange argument you can feel.

Tier 1 · Intervals — the flagship family medium#

1. Non-overlapping Intervals↗ Activity selection; derive "sort by end" via the widget's counterexamples.
2. Minimum Arrows to Burst Balloons↗ The same sweep; practice the inclusive/strict endpoint decision.
3. Merge Intervals↗ → Meeting Rooms II↗ Contrast: sort by start; then the heap/event sweep for concurrency.

Tier 2 · One-pass reach & reset medium#

1. Jump Game↗ → Jump Game II↗ Farthest-reach frontier; then the level-boundary min-jumps greedy.
2. Gas Station↗ Running-tank reset; prove why skipping the bad prefix is safe.
3. Maximum Subarray↗ Kadane as the cleanest reset-greedy; drop a negative prefix.

Tier 3 · Structures & harder proofs hard#

1. Connect Sticks (Huffman)↗ First heap-driven greedy; the two-smallest exchange argument.
2. Remove K Digits↗ Monotonic-stack greedy; building an extremal subsequence.
3. Candy↗ Two-pass greedy with both-sides constraints.
4. Course Schedule III↗ Sort by deadline + max-heap "undo the longest" — the peak heap greedy.

Tier 4 · Graph greedies & constructions hard#

1. Min Cost to Connect All Points↗ MST / cut property; Kruskal with DSU or Prim with a heap.
2. Network Delay Time↗ Dijkstra as greedy shortest path; contrast with MST.
3. Largest Number↗ Pairwise custom comparator + proving it's a valid order.

15 · Cheat sheets#

Everything compressed. Screenshot these; they're the residue of the whole page.

The Discovery Engine, on one line each#

Recognition checklist — "should I reach for greedy?"#

• Objective is optimize / count / feasibility over a set of choices.
• There's a dominant first move you can argue no optimum is hurt by taking.
• After committing, the past collapses to a tiny summary (lastEnd, running total, a heap).
• You cannot build a case where a locally-worse move wins globally (if you can → DP).
• "Sort then sweep" or "repeatedly take the extreme" smells natural.

Sort-key heuristics — what dominance implies#

Proof templates — fill in the blanks#

Greedy vs DP — the one-question decision#

The mistakes that cost the most#