Greedy Algorithms: Betting on Local Optimum

Chapter 26: Greedy Algorithms — Betting on Local Optimum

You are on a circular highway with gas stations, your tank empty. Each station offers different amounts of gas, and the fuel cost to the next station varies. Can you complete the circuit? If so, which station should you start from?

This is the setup of LeetCode #134 (Gas Station). An intuitive approach: start from some station, and if your tank goes negative at station i, then no station between your start and i can work either—skip directly to i+1 and restart. This "skip all intermediate stations" decision seems reckless, but it is correct. This is the essence of greedy algorithms: make the locally optimal choice, betting it leads to the globally optimal solution.

A greedy algorithm is a strategy that chooses the best-looking option at each step. Unlike dynamic programming, it doesn't consider all subproblem combinations. Unlike backtracking, it doesn't try all possibilities—it looks only at the present, makes a decision, and never looks back.

Why does this "myopic" strategy sometimes yield optimal solutions? The answer: when the problem has the greedy-choice property and optimal substructure, greedy is correct. But the flip side: when these properties don't hold, greedy produces wrong answers—and its errors are often subtle. The code runs, results look reasonable, but they're not optimal.

Greedy's history traces to early graph theory. Kruskal's and Prim's algorithms for minimum spanning trees in the 1930s-50s are textbook greedy examples (we covered these in Chapter 18). In 1952, David Huffman, a graduate student at MIT, invented Huffman coding, pioneering greedy methods in information theory. Today, gzip, JPEG, and MP3—ubiquitous compression formats—all directly or indirectly depend on Huffman coding.

This chapter starts from greedy's core idea and correctness proofs, builds deep understanding through classic problems (activity selection, interval scheduling, Huffman coding, knapsack), and concludes with a decision framework for "when to use greedy vs. DP."

Level 1 · What You Need to Know

26.1 Core Idea of Greedy

26.1.1 What is Greedy

The greedy algorithm can be summarized in one sentence:

At each step, make the locally optimal choice, hoping these local choices combine into a globally optimal solution.

Key characteristics:

1. No backtracking: once a choice is made, it's never undone
2. No future consideration: decisions based only on current information
3. No subproblem combination: unlike DP, doesn't merge subproblem solutions

Greedy is the "simplest" algorithmic paradigm—implementations are usually short, time complexity usually excellent. The difficulty lies in: determining whether the greedy strategy is correct.

26.1.2 Greedy vs Dynamic Programming vs Backtracking

                Consider all possibilities?  Exploit overlapping subproblems?  Irreversible choices?
Backtracking:        Yes                          No                              No (backtracks)
DP:                  Yes (implicitly)             Yes                              No
Greedy:              No                           Not needed                       Yes

An intuition:

• Greedy: commit to one path, never look back
• DP: explore every fork, remember the best
• Backtracking: try every path, turn back if stuck

26.2 Activity Selection Problem

26.2.1 Problem Definition

Given n activities, each with start time s[i] and finish time f[i]. A person can attend only one activity at a time. Question: what's the maximum number of non-overlapping activities?

This is greedy's most classic introductory problem, also called "Interval Scheduling."

26.2.2 Greedy Strategy: Sort by Finish Time

Intuition: always select the activity that finishes earliest. Why? Because the earlier an activity ends, the more time remains for subsequent activities.

def activity_selection(activities):
    """
    Activity selection: greedy approach
    activities: [(start, end), ...]
    Returns maximum set of non-overlapping activities
    """
    # Sort by finish time
    sorted_acts = sorted(activities, key=lambda x: x[1])

    selected = [sorted_acts[0]]
    last_end = sorted_acts[0][1]

    for start, end in sorted_acts[1:]:
        if start >= last_end:  # Non-overlapping
            selected.append((start, end))
            last_end = end

    return selected


# Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
              (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"Maximum activities: {len(result)}: {result}")
# Maximum activities: 4: [(1, 4), (5, 7), (8, 11), (12, 16)]

Time complexity: O(n log n) (sorting) + O(n) (scanning) = O(n log n)

26.2.3 Why Other Greedy Strategies Fail

• Sort by start time, pick earliest starting? Wrong! An activity might start at dawn and end at midnight, blocking the entire day.
• Sort by duration, pick shortest? Wrong! A short activity might sit exactly between two long ones—choosing it rejects both.
• Sort by conflict count, pick least conflicting? Seems reasonable, but counterexamples exist.

Only "earliest finish time" is correct. Why? We prove rigorously in Level 2.

26.3 Interval Scheduling Problems

Interval scheduling generalizes activity selection. Three common variants:

26.3.1 Maximum Non-Overlapping Intervals (= Activity Selection)

def max_non_overlapping(intervals):
    """Maximum non-overlapping intervals (inverse of LeetCode #435)"""
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])
    count = 1
    last_end = intervals[0][1]
    for start, end in intervals[1:]:
        if start >= last_end:
            count += 1
            last_end = end
    return count

26.3.2 Minimum Removals for Non-Overlapping (LeetCode #435)

def erase_overlap_intervals(intervals):
    """
    LeetCode #435: Non-overlapping Intervals
    Return minimum number of intervals to remove so remaining don't overlap
    """
    if not intervals:
        return 0
    max_keep = max_non_overlapping(intervals)
    return len(intervals) - max_keep


# Example
intervals = [[1,2],[2,3],[3,4],[1,3]]
print(erase_overlap_intervals(intervals))  # 1 (remove [1,3])

26.3.3 Minimum Arrows to Burst Balloons (LeetCode #452)

def find_min_arrow_shots(points):
    """
    LeetCode #452: Minimum Number of Arrows to Burst Balloons
    Each point is a balloon's horizontal interval [x_start, x_end]
    An arrow at x bursts all balloons containing x
    """
    if not points:
        return 0

    # Sort by right endpoint
    points.sort(key=lambda x: x[1])

    arrows = 1
    arrow_pos = points[0][1]

    for start, end in points[1:]:
        if start > arrow_pos:  # Current balloon not covered
            arrows += 1
            arrow_pos = end

    return arrows


# Example
points = [[10,16],[2,8],[1,6],[7,12]]
print(find_min_arrow_shots(points))  # 2

Key insight: All three problems share the core technique of "sort by right endpoint + greedy selection." They look different but are mathematically equivalent.

26.4 Jump Game

26.4.1 LeetCode #55: Jump Game (Can You Reach the End?)

Given array nums where nums[i] is the maximum jump length from position i. Determine if you can reach the last position.

def can_jump(nums):
    """
    LeetCode #55: Jump Game
    Greedy: maintain the farthest reachable position
    """
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False  # Current position unreachable
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= len(nums) - 1:
            return True
    return True


# Examples
print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False

26.4.2 LeetCode #45: Jump Game II (Minimum Jumps)

def jump(nums):
    """
    LeetCode #45: Jump Game II
    Greedy: within each jump's reachable range, choose position that jumps farthest
    """
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0    # Farthest boundary of current jump
    farthest = 0       # Farthest reachable by next jump

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:  # Must jump now
            jumps += 1
            current_end = farthest
            if current_end >= len(nums) - 1:
                break

    return jumps


# Example
print(jump([2, 3, 1, 1, 4]))  # 2 (0->1->4)

Greedy strategy explained: Think of the array as "platforms." From position 0, your reachable range is [1, nums[0]]. Within that range, find the position that lets you jump farthest—that's where to go next. This is like BFS level expansion: each "jump" corresponds to one BFS level.

26.5 Common Greedy Patterns

Level 2 · How It Works Under the Hood

26.6 Proving Greedy Correctness

The hardest part of greedy is not implementation but proving correctness. Two classic proof techniques:

26.6.1 Exchange Argument

Idea: Assume an optimal solution OPT differs from greedy solution G. Show we can "exchange" a choice in OPT for greedy's choice without making things worse. Repeat until OPT becomes G, proving G is also optimal.

Proof for activity selection:

Let greedy's selection be G = {g₁, g₂, ..., gₖ} (sorted by finish time). Let any optimal solution be OPT = {o₁, o₂, ..., oₘ} (sorted by finish time).

We prove k = m (greedy selects as many as optimal).

Step 1: Show f(g₁) ≤ f(o₁) (greedy's first activity finishes no later)

• Greedy picks the earliest-finishing activity, so f(g₁) ≤ f(o₁)

Step 2: Replace o₁ with g₁ to get OPT' = {g₁, o₂, ..., oₘ}

• Since f(g₁) ≤ f(o₁), and o₂ doesn't overlap o₁ (s(o₂) ≥ f(o₁))
• So s(o₂) ≥ f(o₁) ≥ f(g₁), meaning g₁ doesn't overlap o₂ either
• OPT' is still valid, with |OPT'| = |OPT| = m

Step 3: Recursively apply the same argument to {o₂, ..., oₘ}

• Subproblem: select maximum non-overlapping activities after g₁ ends
• Greedy picks earliest-finishing in subproblem (g₂)
• Similarly replace o₂ with g₂...

Step 4: By induction, k ≥ m. Since OPT is optimal (m is maximum), k ≤ m. Therefore k = m.

26.6.2 Proof by Contradiction

Idea: Assume greedy's solution is not optimal, derive a contradiction.

Proof for Jump Game II (#45):

Let greedy jump k times. Assume a better solution jumps j < k times.

Greedy's property: after jump t, its reachable boundary current_end_t is the farthest position reachable by ANY t-jump strategy.

Proof (by induction):

• After jump 1, greedy's farthest ≥ any other strategy's (greedy picked the farthest-reaching position within range)
• Assume after jump t, greedy's position ≥ other strategies' (induction hypothesis)
• Jump t+1: greedy starts from a farther position, has larger range, so after t+1 still ≥ others

If the better solution reaches the end in j jumps, and greedy reaches at least as far at every step, then greedy also reaches the end in j steps. This contradicts "greedy needs k > j steps."

26.7 Huffman Coding

26.7.1 Background

Suppose you want to compress a file containing only characters a, b, c, d, e. Fixed-length encoding:

• 5 characters need 3 bits (⌈log₂5⌉ = 3)
• 100 characters need 300 bits

But what if character frequencies differ? Say a appears 45 times, b 13 times, c 12 times, d 16 times, e 9 times, f 5 times.

Give high-frequency characters short codes and low-frequency ones long codes to reduce total bits. This is Huffman coding—a prefix-free code where no character's code is a prefix of another's, enabling unambiguous decoding.

26.7.2 Huffman Algorithm

Greedy strategy: always merge the two lowest-frequency nodes.

import heapq
from collections import Counter


class HuffmanNode:
    """Huffman tree node"""
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq


def build_huffman_tree(text):
    """
    Build Huffman tree
    Greedy: always merge the two lowest-frequency nodes
    """
    freq = Counter(text)
    if len(freq) == 0:
        return None
    if len(freq) == 1:
        char = list(freq.keys())[0]
        return HuffmanNode(char=char, freq=freq[char])

    # Create min-heap
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq.items()]
    heapq.heapify(heap)

    # Greedy merging
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        merged = HuffmanNode(
            freq=left.freq + right.freq,
            left=left,
            right=right
        )
        heapq.heappush(heap, merged)

    return heap[0]


def generate_codes(root):
    """Generate code table from Huffman tree"""
    codes = {}

    def traverse(node, code):
        if node is None:
            return
        if node.char is not None:
            codes[node.char] = code if code else '0'
            return
        traverse(node.left, code + '0')
        traverse(node.right, code + '1')

    traverse(root, '')
    return codes


def huffman_encode(text):
    """Huffman encoding"""
    tree = build_huffman_tree(text)
    codes = generate_codes(tree)
    encoded = ''.join(codes[c] for c in text)
    return encoded, codes, tree


def huffman_decode(encoded, tree):
    """Huffman decoding"""
    decoded = []
    node = tree
    for bit in encoded:
        if bit == '0':
            node = node.left
        else:
            node = node.right
        if node.char is not None:
            decoded.append(node.char)
            node = tree
    return ''.join(decoded)


# Complete example
text = "aaaaaaaaaaaaaabbbbbbbbbbcccccccccddddddddddddeeeeeffff"
encoded, codes, tree = huffman_encode(text)

print("Character code table:")
for char, code in sorted(codes.items()):
    print(f"  '{char}': {code}")

print(f"\nOriginal length: {len(text)} characters")
print(f"Fixed encoding: {len(text) * 3} bits (3 bits/char)")
print(f"Huffman encoding: {len(encoded)} bits")
print(f"Compression ratio: {len(encoded) / (len(text) * 8) * 100:.1f}%")

# Verify decoding
decoded = huffman_decode(encoded, tree)
assert decoded == text
print(f"Decode verification: {'passed' if decoded == text else 'failed'}")

26.7.3 Huffman Coding and gzip

gzip's compression pipeline:

1. LZ77: Use sliding window to find repeated strings, replace with (distance, length) pairs
2. Huffman coding: Encode LZ77's output with Huffman codes

gzip uses two Huffman modes:

• Static Huffman: Predefined code table (specified in RFC 1951)
• Dynamic Huffman: Build optimal code table per data block (table stored in compressed data)

# Core Deflate algorithm flow (simplified)
def deflate_simplified(data):
    """Simulating gzip's Deflate compression (minimal version)"""
    # Step 1: LZ77 — find repeats, produce (literal/length, distance) sequence
    lz77_output = lz77_compress(data)

    # Step 2: Huffman — encode LZ77 output
    huffman_encoded = huffman_encode_lz77(lz77_output)
    return huffman_encoded


def lz77_compress(data, window_size=32768, lookahead_size=258):
    """LZ77 compression (simplified)"""
    output = []
    i = 0
    while i < len(data):
        best_length = 0
        best_distance = 0

        search_start = max(0, i - window_size)
        for j in range(search_start, i):
            length = 0
            while (i + length < len(data) and
                   length < lookahead_size and
                   data[j + length] == data[i + length]):
                length += 1
            if length > best_length:
                best_length = length
                best_distance = i - j

        if best_length >= 3:
            output.append(('match', best_distance, best_length))
            i += best_length
        else:
            output.append(('literal', data[i]))
            i += 1

    return output

26.8 Fractional Knapsack vs 0-1 Knapsack

This is the best example for understanding "when greedy works and when it doesn't."

26.8.1 Fractional Knapsack — Greedy Works

Items can be "cut"—you can take a fraction.

def fractional_knapsack(capacity, items):
    """
    Fractional knapsack: greedy
    items: [(weight, value), ...]
    Can take fractions of items
    """
    # Sort by value-per-weight (descending)
    items_with_ratio = [(v / w, w, v) for w, v in items]
    items_with_ratio.sort(reverse=True)

    total_value = 0
    remaining = capacity

    for ratio, weight, value in items_with_ratio:
        if remaining <= 0:
            break
        if weight <= remaining:
            total_value += value
            remaining -= weight
        else:
            total_value += ratio * remaining
            remaining = 0

    return total_value


# Example
items = [(10, 60), (20, 100), (30, 120)]  # (weight, value)
capacity = 50
print(f"Maximum value: {fractional_knapsack(capacity, items)}")
# Maximum value: 240.0
# Take all item1(60) + all item2(100) + 2/3 item3(80) = 240

Why greedy is correct: Because items are divisible, the "highest unit value" strategy wastes no space. Every unit of capacity is filled with the most valuable material.

26.8.2 0-1 Knapsack — Greedy Fails

Items are indivisible—take it or leave it.

# Counterexample: greedy strategy fails
items = [(10, 60), (20, 100), (30, 120)]  # (weight, value)
capacity = 50

# Greedy (by unit value):
# Item1: ratio=6, take (w=10, v=60)
# Item2: ratio=5, take (w=20, v=100)
# Item3: ratio=4, remaining 20<30, can't take
# Greedy result: items 1+2, value=160

# Optimal: items 2+3, weight=50, value=220
# Greedy is far from optimal!

def knapsack_01_dp(capacity, items):
    """0-1 knapsack: requires DP"""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= weight:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)

    return dp[n][capacity]


print(f"0-1 knapsack optimal: {knapsack_01_dp(50, items)}")  # 220

Why greedy fails: Because items are indivisible, choosing a "high unit-value but light" item may leave capacity that can only partially fit a "low unit-value but high total-value" item—and 0-1 knapsack doesn't allow fractions. Greedy cannot handle this "combination effect."

26.9 Quick Reference: When Greedy Applies

Signals that greedy works:

1. Problem asks for "maximum/minimum/optimal"
2. Each step's choice doesn't invalidate previous choices
3. A simple sorting criterion exists
4. Problem has "exchange won't improve" property

Signals that greedy won't work:

1. Current choice affects "quality" of future options
2. Need to consider "combinations" of choices
3. "Choosing A forces B later, but choosing C allows D+E later" scenarios exist
4. Optimal solution doesn't satisfy "subproblem independence"

Level 2 (continued) · More Practice

26.10 Assign Cookies (LeetCode #455)

def find_content_children(g, s):
    """
    LeetCode #455: Assign Cookies
    g[i]: greed factor of child i
    s[j]: size of cookie j
    Each child gets at most one cookie. Cookie j satisfies child i iff s[j] >= g[i]
    Return maximum number of satisfied children
    
    Greedy: use smallest sufficient cookie for least greedy child
    """
    g.sort()
    s.sort()

    child = 0
    cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1

    return child


# Examples
print(find_content_children([1, 2, 3], [1, 1]))  # 1
print(find_content_children([1, 2], [1, 2, 3]))  # 2

Correctness intuition: If a large cookie can satisfy a small appetite, using a just-enough smaller cookie for that child and saving the large one for a bigger appetite is never worse. This is the exchange argument in intuitive form.

26.11 Gas Station (LeetCode #134)

def can_complete_circuit(gas, cost):
    """
    LeetCode #134: Gas Station
    gas[i]: fuel available at station i
    cost[i]: fuel needed to reach station i+1
    Return starting station index for complete circuit, or -1
    
    Greedy:
    1. If total gas >= total cost, solution exists
    2. If starting from 'start', tank goes negative at i, then no station
       between start and i works (they had non-negative tank getting there,
       starting from them means less fuel, still negative at i)
    3. Restart from i+1
    """
    total_tank = 0
    current_tank = 0
    start = 0

    for i in range(len(gas)):
        net = gas[i] - cost[i]
        total_tank += net
        current_tank += net

        if current_tank < 0:
            start = i + 1
            current_tank = 0

    return start if total_tank >= 0 else -1


# Example
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(can_complete_circuit(gas, cost))  # 3

Why "skip all intermediate stations" is correct:

Let starting from 'start', at position j (start <= j <= i) the tank is tank_j >= 0. At position i, tank_i < 0.

If we start from j instead, the tank at i = tank_i - tank_j <= tank_i < 0 (since tank_j >= 0).

So starting from any position between start and i, the tank is still negative at i. Only stations after i can be valid starting points.

26.12 Huffman Correctness Proof

Theorem: Huffman's algorithm builds an optimal prefix code (minimum total encoding length).

Proof (Exchange Argument):

Let alphabet size be n, characters sorted by frequency f₁ ≤ f₂ ≤ ... ≤ fₙ.

Lemma 1: In an optimal tree, the two lowest-frequency characters are at the deepest level and are siblings.

By contradiction: Suppose in optimal tree T, lowest-frequency x is not at the deepest level. Let z be at the deepest level (frequency >= x). Swap x and z: cost change = (f_x - f_z)(depth_z - depth_x). Since f_x <= f_z and depth_z > depth_x, change <= 0, meaning cost doesn't increase. Contradicts T being optimal (unless cost is unchanged, meaning x can also be at deepest level).

Lemma 2: Merging the two lowest-frequency characters yields a subproblem whose optimal solution corresponds to the original problem's optimal.

Let x, y be lowest-frequency, merged into z (f_z = f_x + f_y). Let T be original optimal tree, T' be the tree with x,y's parent replaced by leaf z.

cost(T) = cost(T') + f_x + f_y

If T' is not optimal for the n-1 character problem, let T'' be optimal. Expanding z in T'' back to x,y gives cost = cost(T'') + f_x + f_y < cost(T') + f_x + f_y = cost(T), contradicting T's optimality.

Therefore T' is optimal for n-1 characters. QED by induction.

Level 3 · What the Specifications Define

26.13 Huffman's 1952 Paper

David A. Huffman published "A Method for the Construction of Minimum-Redundancy Codes" (Proceedings of the IRE, 1952). The paper originated from a homework assignment in Robert Fano's class at MIT—Fano gave students two choices: take the final exam, or find the optimal binary encoding method. Huffman chose the latter and, after months of effort, discovered the greedy algorithm.

Ironically, Fano himself had previously proposed Shannon-Fano coding (top-down splitting) which is NOT optimal, while his student's bottom-up merging approach IS optimal. This story perfectly illustrates that "bottom-up greedy" is sometimes better than "top-down divide and conquer."

Core contributions of Huffman's paper:

1. Proved prefix code optimality is achievable through greedy construction
2. Gave an O(n log n) construction algorithm
3. Proved Huffman coding's average code length satisfies H(X) <= L < H(X) + 1, where H(X) is source entropy

The bound H(X) <= L < H(X) + 1 comes from Shannon's 1948 information theory paper. It tells us: Huffman coding is at most 1 bit/symbol more than the theoretical limit (entropy). Modern arithmetic coding can approach entropy, but Huffman coding remains widely used for its simplicity and efficiency.

26.14 Greedy and Matroid Theory

26.14.1 What is a Matroid

A matroid is a combinatorial structure proposed by Hassler Whitney in 1935 to abstract the concept of "independence." A matroid M = (S, I) consists of finite set S and family of independent sets I ⊆ 2^S, satisfying:

1. Empty set is independent: emptyset in I
2. Hereditary property: if A in I and B subset of A, then B in I
3. Exchange property: if A, B in I and |A| < |B|, there exists x in B\A such that A union {x} in I

26.14.2 Greedy is Always Optimal on Matroids

Theorem (Rado 1957, Edmonds 1971): If a problem's feasible solutions form a matroid and the objective is to maximize weight, then greedily adding elements by decreasing weight (maintaining independence) yields the optimal solution.

This theorem explains why these greedy algorithms are correct:

Kruskal's MST (Chapter 18):

• S = all edges
• I = {A subset of S : edges in A form no cycle} (forests)
• This forms a "graphic matroid"
• Greedy: add edges by increasing weight, skip cycle-forming ones
• Correctness guaranteed by matroid theorem

Activity selection (this chapter):

• Strictly speaking, activity selection isn't directly a matroid problem
• But it can be transformed via "interval graph coloring"
• The simpler proof uses exchange argument directly

26.14.3 General Greedy Framework on Matroids

def greedy_on_matroid(elements, weight_fn, is_independent):
    """
    Greedy algorithm on matroid (general framework)
    
    elements: ground set S
    weight_fn: weight function w: S -> R
    is_independent: function testing if subset is independent
    
    Returns maximum-weight independent set
    """
    # Sort by weight descending
    sorted_elements = sorted(elements, key=weight_fn, reverse=True)

    result = set()
    for e in sorted_elements:
        if is_independent(result | {e}):
            result.add(e)

    return result


# Example: Kruskal's algorithm
def kruskal_via_matroid(n, edges):
    """Kruskal using matroid framework"""

    class UnionFind:
        def __init__(self, n):
            self.parent = list(range(n))
            self.rank = [0] * n

        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x, y):
            px, py = self.find(x), self.find(y)
            if px == py:
                return False
            if self.rank[px] < self.rank[py]:
                px, py = py, px
            self.parent[py] = px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1
            return True

    uf = UnionFind(n)
    edges.sort(key=lambda e: e[2])
    mst = []
    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, w))
    return mst

26.15 Matroid Proof of Kruskal's Correctness

In Chapter 18 we proved Kruskal's correctness using the "cut property." Here we give an alternative perspective via matroid theory.

Graphic matroid definition:

• S = all edges of graph
• I = {A subset of S : edges in A form no cycle} (A is a forest)

Verify three axioms:

1. Empty set is a forest ✓
2. Subset of a forest is a forest ✓
3. Exchange property: Let A, B be forests with |A| < |B|. A has n-1-|A| components, B has n-1-|B| components. Since |A| < |B|, A has more components. There must exist edge e in B\A connecting two different components of A, so A union {e} is still acyclic ✓

Applying Rado's theorem: For MST, we want to minimize total weight, equivalent to maximizing "negative weight." By Rado's theorem, greedy (selecting by increasing weight, skipping cycle-forming edges) produces the maximum-weight independent set = minimum spanning tree.

26.16 Theoretical Boundary: Greedy vs DP

From computational complexity:

• Greedy: typically O(n log n)—sort then linear scan
• DP: typically O(n squared) or O(n times W)—table filling
• If a problem admits both greedy and DP, greedy is always faster

From problem structure (CLRS classification):

• Greedy-choice property: global optimum contains locally optimal choices
• Optimal substructure: optimal solution's subproblem solutions are also optimal for those subproblems
• DP needs only optimal substructure
• Greedy needs BOTH greedy-choice property AND optimal substructure

This explains an important phenomenon: problems solvable by greedy are always solvable by DP (DP is more general), but problems solvable by DP are not always solvable by greedy (greedy is more restrictive).

Level 4 · Edge Cases and Pitfalls

26.17 Interview Problem Collection

26.17.1 LeetCode #455: Assign Cookies

(Covered in detail in 26.10)

Key: Sort both arrays + two pointers. Time O(n log n + m log m), Space O(1).

26.17.2 LeetCode #435: Non-overlapping Intervals

(Covered in detail in 26.3.2)

Key: Transform to "maximum non-overlapping count"; answer = total - max non-overlapping.

26.17.3 LeetCode #452: Minimum Arrows to Burst Balloons

(Covered in detail in 26.3.3)

Key: Equivalent to "maximum non-overlapping" (note boundary: touching counts as overlapping).

26.17.4 LeetCode #134: Gas Station

(Covered in detail in 26.11)

Key: Total sum for feasibility + local reset for finding start.

26.17.5 More Interview Greedy Problems

def lemonade_change(bills):
    """
    LeetCode #860: Lemonade Change
    Customers pay 5/10/20 dollars in order, lemonade costs 5
    Can you make change for everyone?
    
    Greedy: prefer using larger bills for change
    """
    five = ten = 0
    for bill in bills:
        if bill == 5:
            five += 1
        elif bill == 10:
            if five == 0:
                return False
            five -= 1
            ten += 1
        else:  # 20
            # Prefer 10+5 change (greedy: keep more 5s)
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False
    return True


def partition_labels(s):
    """
    LeetCode #763: Partition Labels
    Partition string into maximum fragments where each letter appears in only one fragment
    
    Greedy: extend right boundary to farthest occurrence of any included character
    """
    last = {c: i for i, c in enumerate(s)}

    partitions = []
    start = end = 0

    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            partitions.append(end - start + 1)
            start = end + 1

    return partitions


def reorganize_string(s):
    """
    LeetCode #767: Reorganize String
    Rearrange so no two adjacent characters are same. Return "" if impossible.
    
    Greedy + priority queue: always place highest-frequency (different from previous) character
    """
    from collections import Counter
    import heapq

    freq = Counter(s)
    heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(heap)

    result = []
    prev_count, prev_char = 0, ''

    while heap:
        count, char = heapq.heappop(heap)
        result.append(char)

        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_char))

        prev_count = count + 1
        prev_char = char

    return ''.join(result) if len(result) == len(s) else ''

26.18 When to Use Greedy vs DP

This is the most frequently asked meta-question in interviews. Decision framework:

Step 1: Does the problem have the "greedy-choice property"?

Test: If you make a greedy choice (e.g., "pick the smallest," "pick earliest ending"), can you prove there EXISTS an optimal solution containing this choice?

• If provable → greedy might work
• If counterexample exists → must use DP or other methods

Step 2: Construct counterexamples

# General approach to constructing counterexamples:
# 1. Design small cases with 2-3 elements
# 2. Check if greedy's choice leads to error

# Example: Coin change
# Denominations [1, 5, 10, 25], amount 30
# Greedy: 25+5 = 2 coins ✓
# Denominations [1, 3, 4], amount 6
# Greedy: 4+1+1 = 3 coins ✗ (optimal: 3+3 = 2 coins)
# Conclusion: general coin change can't use greedy (but specific systems can)

Step 3: Classic problem classification

Interview answer template: "Let me first consider if greedy works here. Greedy requires that 'local optimum leads to global optimum.' Let me try [specific greedy strategy]... [prove or find counterexample]... So this problem should use [greedy/DP]."

26.19 Greedy Edge Cases

Traps Where Greedy Looks Right but is Wrong

# Trap 1: Traveling Salesman Problem (TSP)
# "Always go to nearest unvisited city" — greedy!
# But TSP is NP-hard, greedy doesn't guarantee optimal.
# Counterexample: 4 cities at square vertices.

# Trap 2: Longest Increasing Subsequence (LIS)
# "Greedily pick the smallest possible" — not correct!
# LIS needs DP (O(n^2)) or greedy+binary search (O(n log n),
# but this "greedy" is essentially DP in disguise)

# Trap 3: Task assignment
# "Give fastest person the heaviest task" — not always right!
# Depends on objective (minimize makespan vs minimize total time)

Cases Where Greedy is Correct but Hard to Prove

def max_profit_job_scheduling(startTime, endTime, profit):
    """
    LeetCode #1235: Job Scheduling for Maximum Profit
    Looks like greedy (sort by end, pick most profitable), but needs DP.
    
    This is "Weighted Interval Scheduling" — different weights
    make simple greedy fail.
    """
    import bisect

    jobs = sorted(zip(endTime, startTime, profit))
    n = len(jobs)
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        end, start, p = jobs[i - 1]
        k = bisect.bisect_right([j[0] for j in jobs[:i]], start)
        dp[i] = max(dp[i - 1], dp[k] + p)

    return dp[n]

26.20 Connections to Other Chapters

• Chapter 18 (Shortest Paths and MST) — Kruskal's and Prim's algorithms are classic greedy applications. Kruskal's correctness can be elegantly proved using matroid theory from this chapter.
• Chapter 25 (Dynamic Programming) — DP is greedy's "enhanced version." When greedy is incorrect, DP is the fallback. Understanding the boundary between them is a core algorithm interview skill.
• MySQL book on this site — Huffman coding is used in InnoDB compressed pages (COMPRESS). InnoDB page compression uses zlib, which internally is LZ77 + Huffman.

Chapter Summary

Greedy is the most "daring" algorithmic paradigm—it makes irreversible locally-optimal choices at each step, betting they combine into a global optimum. This bet sometimes pays off (activity selection, Huffman coding, Kruskal) and sometimes doesn't (0-1 knapsack, TSP, general coin change).

The ability to distinguish when greedy is correct is a core algorithmic literacy. Key takeaways:

1. Three greedy requirements: Greedy-choice property + optimal substructure + no aftereffects
2. Proof methods: Exchange argument (most common) and proof by contradiction
3. Core patterns: Interval scheduling by right endpoint, Huffman merges minimum, knapsack by unit value
4. Decision framework: Try greedy → construct counterexample → if fails, use DP
5. Mathematical foundation: Matroid theory provides the complete theoretical framework for "when greedy is correct"

Huffman in 1952 changed information theory with a homework assignment; Bayer in 1972 changed databases with B-Tree; O'Neil in 1996 changed storage with LSM-Tree. These profoundly impactful contributions often have stunningly simple core ideas—this is the aesthetics of greedy: solving the most complex problems with the simplest rules.