03 — Greedy Algorithms

Phase 5 | Week 32 | Mar 9 – Mar 15, 2027

Greedy is deceptively simple to describe and deceptively easy to get wrong. The idea: at every decision point, make the locally optimal choice. The hard part: proving that locally optimal choices accumulate into a globally optimal solution. Most people use greedy by intuition and get burned when it fails. The exchange argument is the proof technique that distinguishes “I think greedy works here” from “I can demonstrate that it works here.” For FAANG interviews, you need the latter.

What Greedy Is (and Isn’t)

Greedy is: A strategy where you make the best available choice at each step without reconsidering previous choices.

Greedy is NOT: Approximate. When a greedy algorithm is correct, it finds the exact optimal solution. When it’s incorrect, it can be arbitrarily wrong.

The question you must answer for any greedy claim: “Is there ever a situation where taking the non-greedy choice now leads to a better outcome later?” If yes, greedy fails. If provably no, greedy is correct.

The Exchange Argument

This is the canonical proof technique for greedy algorithms. The structure:

  1. Assume an optimal solution O exists.

  2. If O already matches the greedy solution G, done.

  3. Otherwise, O and G differ at some step. Find the first step where they differ.

  4. Show that you can “exchange” O’s choice at that step with G’s choice without making the solution worse (and possibly making it better).

  5. Repeat until O has been transformed into G without loss of quality.

  6. Conclude: G is optimal.

You don’t need to execute this formally in an interview — but understanding it lets you quickly verify whether your greedy intuition is sound.

Canonical Problem 1: Activity Selection

Problem: n activities with start and end times. Select the maximum number of non-overlapping activities.

Greedy strategy: Always pick the activity that ends earliest (among those compatible with already-selected activities).

Exchange argument: Suppose an optimal solution picks activity A before activity B, where B ends before A. Replacing A with B in the solution: B ends earlier, leaving more room for future activities → the solution is at least as good. Repeat: any optimal solution can be transformed to match greedy without losing activities.

Implementation:

activities.sort(key=lambda x: x[1])  # sort by end time
selected = []
last_end = -inf
for start, end in activities:
    if start >= last_end:
        selected.append((start, end))
        last_end = end

O(n log n) for sort, O(n) for selection. The sort is the bottleneck.

Canonical Problem 2: Meeting Rooms II

Problem: Given n meetings with start and end times, find the minimum number of conference rooms needed.

Greedy strategy: Use a min-heap of end times. For each new meeting (sorted by start time), if the earliest-ending meeting has already ended, reuse its room. Otherwise, open a new room.

meetings.sort(key=lambda x: x[0])  # sort by start time
heap = []   # min-heap of end times
for start, end in meetings:
    if heap and heap[0] <= start:
        heappop(heap)   # reuse the room that just freed up
    heappush(heap, end)
return len(heap)

The heap always contains the end times of all currently occupied rooms. Its size at termination = minimum rooms needed. O(n log n).

Canonical Problem 3: Jump Game (Greedy Formulation)

Jump Game I (LeetCode 55): Can you reach the last index? For each position, track the farthest index reachable so far. If current position exceeds max_reachable, you’re stuck.

max_reachable = 0
for i in range(n):
    if i > max_reachable:
        return False    # can't reach this position
    max_reachable = max(max_reachable, i + nums[i])
return True

Jump Game II (LeetCode 45): Minimum jumps to reach end. At each position, track the farthest reachable from the current “jump window.” When you exhaust the current window, take a jump and start a new window.

jumps = 0
current_end = 0
farthest = 0
for i in range(n - 1):
    farthest = max(farthest, i + nums[i])
    if i == current_end:
        jumps += 1
        current_end = farthest
return jumps

O(n). No heap needed.

Canonical Problem 4: Huffman Coding

Problem: Given character frequencies, build a prefix-free binary code that minimizes total encoded length. (Tree with characters at leaves; path from root = encoding.)

Greedy strategy: Always merge the two least-frequent symbols into a new node. Use a min-heap.

heap = [(freq, char) for char, freq in frequencies.items()]
heapify(heap)
while len(heap) > 1:
    f1, n1 = heappop(heap)
    f2, n2 = heappop(heap)
    heappush(heap, (f1 + f2, combine(n1, n2)))
return heap[0]

Why it’s correct: Merging the two rarest symbols gives them the longest codes (deepest in the tree), which minimizes total length. Exchange argument: any swap of positions in the tree that moves a less-frequent symbol to a deeper position improves or ties the result.

This is the formal foundation for file compression (DEFLATE, ZIP). Know it conceptually; implementation details vary.

Fractional Knapsack

Problem: Items with weight and value. You can take fractional amounts. Maximize value subject to capacity constraint.

Greedy strategy: Sort by value/weight ratio descending. Take items in that order; take a fraction of the last item if needed.

Why greedy works here but not for 0/1 knapsack: With fractions, taking more of any item and less of a lower-ratio item never helps. With 0/1, you might need a lower-ratio item to fill capacity exactly to enable more valuable items.

When Greedy FAILS: Counterexamples

Always test greedy with at least one counterexample before committing.

Coin change with arbitrary denominations: Denominations [1, 3, 4], target 6.

  • Greedy (take largest): 4 + 1 + 1 = 3 coins.

  • Optimal: 3 + 3 = 2 coins.

Greedy fails because taking 4 doesn’t enable the optimal 3+3 split.

0/1 Knapsack with high-value small items: Greedy by value/weight ratio can leave capacity wasted, missing combinations that fill it completely.

Minimum spanning tree vs. shortest path: Greedy approaches (Prim’s for MST, Dijkstra for shortest path) work, but they’re different greedy criteria. Confusing them produces wrong algorithms.

Greedy vs. DP Decision Protocol

  1. Can you identify a greedy criterion (sort by end time, take smallest, take largest ratio)?

  2. Can you sketch an exchange argument showing the criterion is locally correct?

  3. Can you find a counterexample (small case where greedy gives suboptimal answer)?

If (1) and (2) and no (3): use greedy. O(n log n) instead of O(n²) DP. If (3) exists: use DP. Greedy is wrong. If you can’t decide: try DP first (it’s more general), then check if the DP reduces to a greedy.

Practice Problems

Easy

  1. Assign Cookies — LeetCode 455. Basic activity selection variant. Sort both arrays, two pointers.

  2. Lemonade Change — LeetCode 860. Greedy cash register. Simple but exposes the “locally best” reasoning.

Medium

  1. Jump Game — LeetCode 55. Greedy max-reachable scan.

  2. Meeting Rooms II — LeetCode 253. Min-heap of end times.

  3. Task Scheduler — LeetCode 621. Greedy scheduling with cooldown. Math formula derivation is elegant.

  4. Gas Station — LeetCode 134. Greedy: if total gas ≥ total cost, a solution exists; start from the first node where cumulative surplus ≥ 0.

Hard

  1. IPO — LeetCode 502. Two-heap greedy. Unlock projects by capital, always take highest-profit available. Classic “sorted + heap” greedy pattern.