Greedy Algorithms, in depth: when the locally best choice is globally right, and how to prove it

The shape of a greedy algorithm

Every greedy algorithm has the same skeleton: order the candidates by some key, then walk through them and keep each one that is still feasible given what you kept so far.

def greedy(candidates, key, feasible):
    solution = []
    for c in sorted(candidates, key=key):
        if feasible(solution, c):
            solution.append(c)      # commit; never undone
    return solution

The whole design problem is choosing the key. The loop is trivial; the correctness argument is not. Two properties must hold for the result to be optimal:

• Greedy-choice property. Some optimal solution contains the first choice the greedy rule makes. You can commit to that choice without losing optimality.
• Optimal substructure. After committing, what remains is a smaller instance of the same problem, and an optimal solution to it combined with your choice is optimal for the whole.

Optimal substructure is shared with dynamic programming. The difference is the greedy-choice property: DP tries every choice for the current step and keeps the best, while greedy tries exactly one. When the greedy-choice property fails, DP is usually the correct fallback, at the price of a table instead of a scan.

Worked example: activity selection

You run one conference room and have seven talk requests, each with a start and end hour. You want to host as many talks as possible without overlap. Intuitive keys include shortest talk first, earliest start first, and fewest conflicts first. The key that is provably optimal is earliest finish time first.

def select_activities(intervals):
    """intervals: (start, end, name); half-open, so a talk ending at 11 and one starting at 11 fit."""
    chosen, last_end = [], float("-inf")
    for start, end, name in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:
            chosen.append(name)
            last_end = end
    return chosen

talks = [(9, 12, "A"), (10, 11, "B"), (11, 13, "C"), (12, 14, "D"),
         (13, 15, "E"), (14, 16, "F"), (9, 10, "G")]
print(select_activities(talks))   # ['G', 'B', 'C', 'E']

Trace it. Sorted by end time the order is G (ends 10), B (11), A (12), C (13), D (14), E (15), F (16). G is kept. B starts at 10, when G ends, so it is kept. A starts at 9, before B ends, so it is rejected. C starts at 11 and is kept, D overlaps C, E starts at 13 and is kept, F overlaps E. Four talks. The cost is O(n log n) for the sort and O(n) for the scan.

Why not the other keys? Earliest start fails on {(0,10), (1,2), (3,4), (5,6)}: it takes the long talk first and ends with one, while the optimum is three. Shortest first fails on {(0,5), (4,7), (6,11)}: it takes the short middle talk, which blocks both others, and ends with one where two fit. A single counterexample is enough to reject a key, and trying to build one is the fastest test of any greedy idea.

Proving it: the exchange argument

The standard proof technique is the exchange argument: take any optimal solution, show you can swap one of its elements for the greedy choice without making it worse, and repeat until the optimal solution is the greedy one.

For activity selection: let g be the talk with the earliest finish, and let O be any optimal schedule whose first talk is o. Because g finishes no later than o, replacing o with g cannot create an overlap with the rest of O, since everything after o starts after o ends, which is at or after g ends. The new schedule has the same size, so it is also optimal and it contains g. That is the greedy-choice property. Removing g and every talk that overlaps it leaves a smaller instance of the same problem, which is optimal substructure. Induction finishes the proof.

The second technique is greedy stays ahead: show that after each step, the greedy partial solution is at least as good as any other solution's partial solution by some measure. For activity selection the measure is the finish time of the k-th chosen talk: greedy's k-th talk always ends no later than the k-th talk of any valid schedule, so greedy can never run out of room first. Use exchange when you can describe a swap; use stays-ahead when you can describe a progress measure. If you can do neither, be suspicious of the algorithm.

Where greedy fails, with numbers

Three counterexamples are worth memorising because the problems look greedy.

Largest-coin-first is optimal for systems such as {1, 5, 10, 25}, where it pays 63 as 25+25+10+1+1+1, but not for arbitrary denominations. Coin systems where it always works are called canonical, and whether a system is canonical can be checked, but the safe default for arbitrary coins is the DP.

The knapsack case is instructive because the same rule is exactly optimal for the fractional knapsack, where you may take part of an item. Taking the first two whole items and 20/30 of the third gives 60 + 100 + 80 = 240, and no fractional packing beats it. The only difference is divisibility, which is what makes the exchange argument work: you can always swap a sliver of a worse-ratio item for a sliver of a better one. With whole items, that swap does not exist.

Dijkstra's algorithm is greedy: it settles the closest unsettled node and never revisits it. That is correct only if edge weights are non-negative, because then no later path can be shorter than one already settled. With the negative edge B to A, the path S-B-A costs 1, but A was settled at 2 before B was expanded. The fix is not a smarter greedy but a different algorithm: Bellman-Ford relaxes all edges repeatedly and accepts negative weights.

Huffman coding: greedy with a heap

Huffman coding builds an optimal prefix-free code for symbols with known frequencies. The greedy rule is: repeatedly merge the two least frequent subtrees. A binary heap makes each merge O(log n), for O(n log n) overall.

import heapq, itertools

def huffman(freqs):
    tie = itertools.count()                  # breaks ties so tuples never compare trees
    heap = [(f, next(tie), sym) for sym, f in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)
        f2, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tie), (a, b)))
    codes = {}
    def walk(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or "0"
            return
        walk(node[0], prefix + "0")
        walk(node[1], prefix + "1")
    walk(heap[0][2], "")
    return codes

freqs = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}   # in thousands
print(huffman(freqs))
# a=0  c=100  b=101  d=111  f=1100  e=1101

The weighted length is 45x1 + 13x3 + 12x3 + 16x3 + 9x4 + 5x4 = 224 thousand bits, against 300 thousand for a fixed three-bit code, a 25 percent saving. The exchange argument: in some optimal tree the two rarest symbols are siblings at the deepest level, because swapping a rarer symbol deeper never increases cost. Merging them into one symbol of combined frequency gives a smaller instance of the same problem. Note the tie counter in the heap tuples; without it, Python tries to compare a string with a tuple when two frequencies are equal and raises TypeError. Different tie-breaks produce different codes with the same total length, which matters if two systems must agree on the code: ship the code table, not just the frequencies.

Why some greedy algorithms always work: matroids

There is a general theory behind the successes. A matroid is a ground set plus a family of independent subsets that is closed under taking subsets and satisfies the exchange property: if A and B are independent and A is larger, some element of A can be added to B keeping it independent. For any matroid with non-negative weights, the greedy algorithm that adds elements in decreasing weight order whenever independence is preserved finds a maximum-weight independent set. Conversely, if greedy is optimal for every weighting, the structure is a matroid.

The best-known example is the graphic matroid: the ground set is a graph's edges and the independent sets are the forests. Greedy over edges in increasing weight, skipping any edge that would form a cycle, is Kruskal's minimum spanning tree algorithm. The cycle check is a union-find query, so the whole algorithm is a sort plus near-constant-time unions. Scheduling unit-time jobs with deadlines to maximise profit is another matroid, which is why its greedy solution is exact.

The practical use of the theory is a quick sanity test. If your feasibility rule has the exchange property, greedy is safe. If adding an element can make a previously feasible element infeasible in a way that is not a simple subset restriction, as with knapsack capacity, expect greedy to fail.

Greedy as an approximation

Many problems where greedy is not exact are NP-hard, and there greedy is often the best practical algorithm, with a provable bound.

• Set cover. Repeatedly pick the set covering the most uncovered elements. The result is within a factor of H(n), roughly ln n, of optimal, and under standard complexity assumptions no polynomial algorithm does substantially better.
• Monotone submodular maximisation under a cardinality limit. Diminishing-returns objectives, such as coverage of documents for a search result page or sensor placement, get a (1 - 1/e) approximation, about 63 percent, from greedy selection.
• k-center clustering. Pick any point, then repeatedly pick the point farthest from all chosen centres. The maximum radius is at most twice optimal.

When you ship an approximation, record the bound in the code comment and measure the gap on real data against an exact solver on small instances. The worst-case bound is usually pessimistic; the measured gap is what you report.

Implementation patterns and costs

The sort usually dominates, so the asymptotic cost is set by it. When candidates arrive as a stream and you cannot sort, check whether an online version keeps its guarantee; many do not.

Failure modes in real code

• Wrong sort key that passes the tests. Small hand-made inputs rarely contain the counterexample. Property-test the greedy against a brute-force or DP solver on thousands of random small inputs; this catches most wrong keys in seconds.
• Open versus closed intervals. Whether a talk ending at 11 conflicts with one starting at 11 changes the answer. Decide, document it, and use >= or > to match.
• Ties. Equal keys make the output depend on sort stability and input order. The size is still optimal, but downstream systems may see different selections run to run. Add an explicit secondary key.
• Floating-point ratios. Value per weight computed as floats can misorder near-equal items. Compare a/b and c/d as a x d versus c x b on integers.
• Silent regression when requirements change. A weighted variant of activity selection, where talks have different values, breaks earliest-finish greedy and needs DP over sorted intervals. When a product adds weights, priorities or capacities, re-check the proof.

What to do next

1. For any greedy you write, state the key and try to build a counterexample by hand for five minutes before coding.
2. Write the exchange or stays-ahead argument in a code comment. If you cannot, treat the algorithm as a heuristic.
3. Add a property test that compares the greedy with a brute-force or DP solver on random inputs of size 1 to 10.
4. Make interval boundaries and tie-breaking explicit in the code.
5. Re-implement activity selection, Huffman and fractional knapsack from memory, then check your outputs against the numbers in this article.
6. When greedy fails, move to dynamic programming; when the problem is NP-hard, use greedy as an approximation and record its bound.