Greedy Algorithms: When Local Optima Build Global Solutions

A greedy algorithm makes the best immediate choice at each step, hoping the local optima lead to a global optimum. Not all problems have greedy solutions.

When Greedy Works

A greedy algorithm is optimal if the problem has:

1. Optimal substructure: Optimal solution contains optimal solutions to subproblems
2. Greedy choice property: A locally optimal choice leads to a globally optimal solution

The Greedy Test

If you can prove that making the best choice now never prevents finding the optimal solution later, greedy works.

Classic Greedy Problems

1. Fractional Knapsack

Take fractions of items to maximize value within weight limit.

def fractional_knapsack(items, W):
    # items: [(value, weight)]
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total_value = 0
    for value, weight in items:
        if W >= weight:
            total_value += value
            W -= weight
        else:
            total_value += value * (W / weight)
            break
    return total_value

Greedy choice: Take the item with the best value/weight ratio. Time: O(n log n) Optimal: Yes (fractional — not true for 0/1 knapsack).

2. Activity Selection

Select the maximum number of non-overlapping activities.

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

Greedy choice: Pick the activity with the earliest finish time. Time: O(n log n) Optimal: Yes.

3. Huffman Coding

Build an optimal prefix code for data compression.

import heapq

def huffman_coding(freqs):
    heap = [[freq, [char, ""]] for char, freq in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:], key=lambda p: len(p[1]))

Greedy choice: Merge the two least frequent characters. Time: O(n log n) Optimal: Yes.

4. Minimum Spanning Tree (Kruskal’s)

Find the minimum set of edges connecting all vertices.

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # sort by weight
    parent = list(range(n))
    mst = []

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

    def union(x, y):
        parent[find(x)] = find(y)

    for u, v, w in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, w))
    return mst

Greedy choice: Add the smallest edge that doesn’t create a cycle. Time: O(E log E) Optimal: Yes.

5. Dijkstra’s Algorithm

Shortest paths from a single source.

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

Greedy choice: Process the closest unvisited node next. Time: O((V + E) log V) Optimal: Yes (with non-negative weights).

6. Coin Change (Canonical Systems)

Minimum coins to make a target amount.

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1

Greedy choice: Use the largest coin first. Optimal: Only for canonical systems (USD, EUR). Not optimal for arbitrary coin systems (e.g., [1, 3, 4], target 6).

Proof Techniques

Exchange Argument

Show that any optimal solution can be transformed into the greedy solution without losing optimality.

1. Let G be the greedy solution, O be any optimal solution
2. Find the first point where G and O differ
3. Show you can swap O’s choice for G’s choice without making O worse
4. Therefore G is as good as O

Greedy Stays Ahead

Show that the greedy choice never falls behind any optimal solution.

1. After k steps, greedy is at least as far along as any optimal solution
2. By induction, greedy finishes at least as well

When Greedy Fails

Greedy doesn’t work when local choices affect future options:

| Problem | Why Greedy Fails | |

Greedy vs. DP

Rule of thumb: Try greedy first. If you can prove optimality, use it. Otherwise, fall back to DP.

Greedy Algorithm Theory

Exchange Argument Proof Technique

Proving that a greedy algorithm produces the global optimum is harder than designing the algorithm. The exchange argument is the standard proof technique: take an optimal solution and transform it into the greedy solution without worsening the objective. This shows the greedy solution is at least as good as the optimal. For the interval scheduling problem — selecting the maximum number of non-overlapping intervals — the greedy choice is to pick the interval with the earliest finish time. The proof shows that any optimal solution can be transformed to include the earliest-finishing interval without reducing the count of intervals. The matroid theory provides a mathematical framework for when greedy algorithms are guaranteed to produce optimal solutions — the greedy algorithm finds a maximum-weight independent set in a matroid structure.

Matroids and Greedy Optimality

A matroid is a combinatorial structure defined by a ground set and a collection of independent sets satisfying hereditary and augmentation properties. The key result: if a problem can be formulated as finding a maximum-weight independent set in a matroid, the greedy algorithm that repeatedly adds the highest-weight element maintaining independence produces the optimal solution. The minimum spanning tree (Kruskal’s algorithm) is the canonical matroid example — the graphic matroid’s independent sets are acyclic subgraphs. Other matroid examples include the partition matroid (scheduling with deadlines), the transversal matroid (matching in bipartite graphs), and the linear matroid (linearly independent vectors). Recognizing a matroid structure confirms greedy optimality.

When Greedy Fails

Greedy algorithms fail when local optimal choices lead to globally suboptimal solutions. The knapSack problem illustrates this: taking the highest value-to-weight ratio item first (greedy) produces a suboptimal solution when items cannot be divided. The traveling salesman problem with the nearest-neighbor heuristic — always visit the nearest unvisited city — typically produces tours 15-20% longer than optimal. The coin change problem is greedy-optimal for canonical coin systems (US coins) but fails for non-canonical systems (e.g., denominations 1, 3, 4 — greedy gives 4+1+1+1=7 coins for 6, but optimal is 3+3=2 coins). Understanding when to apply greedy versus DP or exhaustive search requires recognizing whether the greedy choice property and optimal substructure both hold — greedy requires the stronger property that a globally optimal solution can be reached by making locally optimal decisions.

Advanced Greedy Examples

Task Scheduling

The weighted interval scheduling problem assigns tasks with start times, end times, and weights to maximize total weight. The greedy earliest-finish-time approach works only when all weights are equal. When tasks have different weights, dynamic programming is needed because the greedy choice property does not hold — a short high-weight task might be skipped in favor of multiple consecutive low-weight tasks. This distinction between equal-weight and weighted variants demonstrates why greedy algorithms require careful verification of the greedy choice property. The scheduling with deadlines problem has a greedy solution using the Earliest Deadline First (EDF) rule when tasks have unit processing time — always schedule the task with the nearest deadline that has not yet been missed. With different processing times, the Moore-Hodgson algorithm schedules to minimize the number of late tasks by ordering by deadline and dropping the longest task when overloaded.

Data Compression

Huffman coding greedily builds an optimal prefix code by repeatedly merging the two lowest-frequency symbols. The algorithm maintains a priority queue of symbol frequencies: at each step, dequeues the two smallest frequencies, creates a new internal node with their sum, and enqueues the combined node. After the tree is built, each symbol’s code is the path from root to leaf, with left edges labeled 0 and right edges labeled 1. Huffman coding achieves compression within one bit per symbol of the entropy of the source distribution and is optimal for symbol-by-symbol encoding with fixed codeword lengths. The algorithm runs in O(n log n) time where n is the number of distinct symbols. Run-length encoding, Lempel-Ziv-Welch (LZW), and other compression methods use different approaches but Huffman coding’s greedy optimality is mathematically proven.

Frequently Asked Questions

What is the difference between greedy algorithms and dynamic programming? Both exploit optimal substructure, but greedy algorithms assume the greedy choice property — the local optimal choice leads to the global optimum — and make irreversible decisions without reconsidering. Dynamic programming explores all possible choices and uses memoization to avoid recalculating overlapping subproblems. DP is more computationally intensive but applies to a wider range of problems.

How do I prove a greedy algorithm is optimal? Use the exchange argument: show that any optimal solution can be transformed step by step into the greedy solution without decreasing optimality. Alternatively, formulate the problem as a matroid — if the feasible sets form a matroid, the greedy algorithm is guaranteed optimal. For some problems, induction on the number of decisions also works.

What are the most common greedy algorithm applications? Minimum spanning tree (Kruskal, Prim), shortest path (Dijkstra), Huffman coding, interval scheduling, fractional knapSack, job sequencing with deadlines, coin change (canonical systems), and activity selection. Each solves an optimization problem where the locally best choice at each step leads to the globally optimal solution.

Sorting Algorithms Guide — Dynamic Programming Guide — Graph Algorithms Guide