Greedy Algorithms

A greedy algorithm is the most human strategy there is: at every step, grab whatever looks best right now and never look back. No planning, no backtracking, no weighing of futures. When it works, it is gloriously fast and simple. The entire art is knowing when it works, because greedy's fatal charm is that it always produces an answer, confidently, whether or not that answer is correct.

It is correct only when the problem has two properties. The greedy-choice property: a locally optimal pick is safe, part of some overall best solution. And optimal substructure: after making that pick, what remains is a smaller version of the same problem. When both hold, grabbing the best local option repeatedly lands you on the global optimum. When they do not, greedy walks off a cliff with a smile.

The archetype: fitting the most activities

The cleanest example is choosing the largest set of non-overlapping activities from a pile with fixed start and end times. The winning instinct is not obvious: you sort by end time and always take the next activity that starts after your last one finished.

def max_activities(activities):
    activities.sort(key=lambda x: x[1])     # earliest finish first
    count, last_end = 0, float("-inf")
    for start, end in activities:
        if start >= last_end:
            count += 1
            last_end = end
    return count

The reason sorting by end time is the right greedy choice, and sorting by start or by duration is not, is an exchange argument: the activity that finishes earliest leaves the most room for everything after it, so choosing it can never cost you a better solution. That little proof is the difference between a greedy algorithm that works and one that merely looks plausible.

Two panels. On the left, activity selection: sorting by finish time and always taking the earliest-finishing compatible activity picks three non-overlapping activities, which is optimal. On the right, making 6 from coins 1, 3 and 4: greedy grabs 4 then 1 then 1 for three coins, but two 3s is better, so the same greedy rule is provably wrong here.

In the wild: Huffman coding

Greedy is not just for toys; it is the engine of real data compression. Huffman coding, which lives inside ZIP, gzip, JPEG, and MP3, builds an optimal set of variable-length codes by being greedy about frequency. The idea: symbols that appear often should get short codes, rare ones long codes. The greedy move is to repeatedly take the two least frequent symbols and merge them into a subtree, over and over, until one tree remains. The two rarest deserve to sit deepest, so merging them first is always safe.

import heapq

def huffman_total_bits(frequencies):
    heap = list(frequencies)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)         # two least frequent
        b = heapq.heappop(heap)
        merged = a + b
        total += merged                 # every symbol under here gains one bit of depth
        heapq.heappush(heap, merged)
    return total

For frequencies [1, 1, 2] this returns 6, exactly the total bits of the optimal tree. It is the same shape as activity selection: a provably safe local choice, taken greedily, that composes into a global optimum. The proof that "merge the two rarest" is safe is another exchange argument, and it is why Huffman is not a heuristic but genuinely optimal for symbol-by-symbol coding. Real compression rides on a greedy algorithm whose correctness someone bothered to prove.

The trigger

An optimization asking for a maximum or minimum, where you can imagine a simple rule for the "best next choice" and a hand-wavy sense that taking it never hurts. Greedy is worth trying first because it is so cheap, but the trigger comes with a duty: before trusting it, argue why the local choice is safe.

Where it shows up

  • Scheduling: activity selection, minimizing lateness, deadline-based job ordering.
  • Encoding and structure: Huffman coding, and building minimum spanning trees.
  • Canonical coin systems: making change with the fewest coins, when the denominations cooperate.

Where it bites

The wound is almost never a bug in the loop; it is trusting greedy where it does not hold. The canonical trap is coin change with awkward denominations. To make 6 from coins [1, 3, 4], greedy grabs the 4, then two 1s, three coins total, while the real optimum is two 3s. The code ran perfectly and gave a worse answer, which is the most dangerous kind of wrong.

When it is the wrong tool

If a locally optimal choice can force a globally worse outcome, greedy is simply invalid, and no amount of tuning fixes it; that is Dynamic Programming territory, where you keep enough state to reconsider. The tell is whether you can prove the greedy-choice property. If you cannot, and especially if a choice's cost depends on choices you have not made yet, do not ship greedy on faith. The honest move when unsure is to try greedy, then look hard for a counterexample, and fall back to DP the moment you find one.

Its neighbors

Greedy almost always rides on Sorting-Based Patterns, since the safe choice is usually "the smallest" or "the earliest" by some key. It is the counterpart to Dynamic Programming: greedy commits and never revisits, DP remembers so it can. And its interval-flavored members share a border with Merge Intervals and Overlapping Intervals.

References