Greedy algorithms

What this chapter covers

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best at that moment and never looking back. When it works, it's the simplest and fastest kind of algorithm — no recursion tree, no table to fill, just a sweep making locally optimal decisions that happen to add up to a globally optimal answer. You've already seen greedy succeed: Dijkstra settles the nearest node, Prim and Kruskal add the cheapest safe edge, Huffman merges the two rarest symbols. This chapter studies the paradigm itself and confronts its central danger — greedy is correct only for the right greedy criterion, and the wrong "best" gives a perfectly plausible algorithm that silently returns worse answers. The showcase is interval scheduling — fit the most non-overlapping activities into one room — where the correct rule (take the earliest-finishing activity) is provably optimal, and two equally intuitive rules (earliest-starting, shortest) are not. The face-off between them is the lesson: in greedy algorithms, the criterion is everything.

A bit of history

Greedy methods are as old as optimization, but their theory — when greedy is guaranteed correct — was worked out in the mid-twentieth century alongside the problems that made them famous. Interval scheduling and its earliest-finish rule are textbook examples going back to the operations-research literature. Huffman coding (1952) is the canonical optimal greedy, proven optimal by an exchange argument. The deepest result is Jack Edmonds's 1971 characterization: greedy algorithms produce optimal solutions exactly for problems whose feasible sets form a matroid, an abstract structure capturing "independence." That theorem draws a precise line between problems where greedy works (minimum spanning trees — the MST is a matroid, so Kruskal's greedy is optimal) and problems where it doesn't, and it explains why the same greedy shape succeeds for MST but fails for, say, the traveling salesman. The practical takeaway predates the theory, though: a greedy algorithm always needs a proof, because it's so easy to write one that seems right and isn't.

The intuition

Interval scheduling asks: given activities with start and finish times, competing for one room, select the most that don't overlap. The greedy idea is to repeatedly pick one activity and commit to it. The question is which one — and there are several tempting answers. Pick the activity that starts earliest? Pick the shortest, to leave room for others? Pick the one that finishes earliest? All three are "greedy," and only the last is correct.

Here's why earliest-finish wins. Sort the activities by finish time and sweep: take the first (it finishes soonest of all), then skip everything that overlaps it, then take the next compatible one (which now finishes soonest of the rest), and so on. The reason this is optimal is an exchange argument: whatever the optimal schedule does first, you can swap its first activity for the earliest-finishing one without any conflict — the earliest-finishing activity ends no later, so it can only free up more room for the rest. Repeat the swap down the schedule and you've transformed the optimum into the greedy's choice without ever reducing the count, which means the greedy is optimal too. The intuition is "finishing early is the most generous thing you can do for everything that comes after," and finish time, not start time or duration, is what measures that generosity. The wrong criteria fail precisely because they optimize the wrong thing: earliest-start can pick one long activity that blocks many; shortest can pick a brief activity in the middle that conflicts with two others that don't conflict with each other.

Complexity: how it scales

The earliest-finish greedy is O(n log n) — a sort by finish time, then a single linear sweep. That's typical of greedy algorithms: the work is a sort (or a priority queue, as in Dijkstra and Prim) plus a pass, with no recursion or memoization. Space is O(n) for the sorted list, O(1) beyond it. But complexity isn't the interesting axis for greedy — correctness is. The face-off doesn't race speed; it races the three greedy criteria on the quality of their answers, counting how many activities each selects:

Earliest-finish is provably optimal — the correctness test confirms it matches a brute-force optimum on every small instance. Earliest-start is dramatically worse: at 64 candidate activities it scheduled about 7.7 against earliest-finish's 13.1, roughly 40% fewer, because one early-starting but late-finishing activity blocks a swath of others. Shortest-first is the sneaky one: on these random inputs it averaged 13.0, almost matching the optimum — close enough that you might ship it and never notice it's wrong. But it is wrong, provably: on the intervals [0,10), [9,11), [10,20), shortest-first grabs the tiny [9,11) first, which overlaps both of the others, scheduling one activity where the optimum schedules two. A greedy that's usually right is still a bug, and "usually right" is exactly what makes the wrong criterion dangerous.

What it's good at, what it isn't

Greedy algorithms are the right choice when a problem has the greedy-choice property and optimal substructure — provably, via an exchange argument or a matroid structure. Then they're unbeatable: simpler, faster (usually just a sort and a sweep), and lower-memory than dynamic programming or search. The classics are all greedy: minimum spanning trees (Prim, Kruskal), shortest paths with non-negative weights (Dijkstra), optimal prefix codes (Huffman), activity/interval scheduling, fractional knapsack, and many scheduling and resource-allocation problems. Greedy is also the backbone of approximation algorithms — even when it can't find the exact optimum, a greedy rule often gets provably close (set cover, vertex cover), which is valuable for NP-hard problems where exact optimization is infeasible.

Where greedy fails is problems lacking the greedy-choice property, and the failures are treacherous because the algorithm still runs and produces a plausible answer. The 0/1 knapsack problem (next chapter) can't be solved greedily — taking the highest value-per-weight item first can be arbitrarily bad — and needs dynamic programming. Coin change is greedy-optimal for some coin systems (like standard currency) but not others: for coins {1, 3, 4} making 6, greedy takes 4+1+1 (three coins) when 3+3 (two) is optimal. The traveling salesman, graph coloring, and most NP-hard problems have no optimal greedy. The rule of thumb: greedy is a hypothesis, not a solution — it needs proof, and if you can't prove the greedy-choice property, assume it's wrong and reach for dynamic programming or search.

The data, or the inputs

The face-off generates random sets of activities in a fixed time window and counts how many each of the three greedy criteria — earliest-finish, earliest-start, shortest — manages to schedule, across a growing number of candidates. Correctness is checked against a brute-force optimum (try every subset) on hundreds of small instances: earliest-finish must always equal the true maximum, and the other two must never exceed it. The animation runs the earliest-finish greedy on the textbook eleven-activity example, drawing the activities as bars on a timeline sorted by finish time and sweeping down, taking each compatible one.

Build it, one function at a time

The optimal greedy — sort by finish time, sweep, take each compatible activity:

def schedule_earliest_finish(intervals):
    """The optimal greedy for interval scheduling: sort activities by FINISH time, then sweep
    left to right taking each activity whose start is not before the last taken finish. Finishing
    early leaves the most room for what follows — that's the intuition the exchange argument makes
    rigorous. O(n log n), dominated by the sort. Returns the chosen intervals."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[1]):   # by finish time
        if start >= last_finish:                 # compatible with everything chosen so far
            chosen.append((start, finish))
            last_finish = finish
    return chosen

And the two plausible-but-wrong criteria, for comparison:

def schedule_earliest_start(intervals):
    """A plausible-but-WRONG greedy: take the activity that starts earliest. One long early
    activity can block many short later ones, so this can badly underperform the optimum."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[0]):   # by start time
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen


def schedule_shortest(intervals):
    """Another plausible-but-WRONG greedy: take the shortest activity first. A short activity in
    the middle can conflict with two others that don't conflict with each other, losing one."""
    chosen = []
    taken = []
    for start, finish in sorted(intervals, key=lambda iv: iv[1] - iv[0]):   # by duration
        if all(finish <= s or start >= f for s, f in taken):        # overlaps nothing chosen
            taken.append((start, finish))
            chosen.append((start, finish))
    return chosen

Watch it work

Here's the earliest-finish greedy scheduling eleven activities, drawn as bars on a timeline and sorted top to bottom by finish time — the order the greedy considers them. The dashed blue line marks the finish time of the last activity taken: the room is free to its right. Sweep down: the first activity [1,4) is taken (green), and the line jumps to time 4. The next few bars start before 4, so they overlap and are skipped (red). [5,7) starts at 5, after the line, so it's taken and the line moves to 7. And so on — the greedy grabs [1,4), [5,7), [8,11), [12,16), four activities, each the earliest-finishing one still compatible. No other selection fits more; that's what the exchange argument guarantees:

The complete code

The from-scratch tab is all three greedy criteria — the optimal earliest-finish and the two wrong ones; the library tab is the brute-force optimum used to verify that earliest-finish is genuinely optimal. Flip between them — the three greedies are nearly identical code, differing only in the sort key, which is exactly the point: the criterion is a one-line change and it's the whole difference between correct and wrong.

"""Greedy algorithms — build a solution by repeatedly making the choice that looks best right
now, never reconsidering. When a problem has the right structure, those locally-best choices add
up to a globally optimal answer, with none of the backtracking or table-filling of the other
paradigms. You've already seen greedy work: Dijkstra settles the nearest node, Prim and Kruskal
add the cheapest safe edge, Huffman merges the two rarest symbols. This chapter studies the
paradigm itself, and the delicate thing about it: greedy is only correct for the RIGHT greedy
criterion, and choosing the wrong "best" gives a plausible algorithm that quietly returns
suboptimal answers.

The showcase is interval scheduling: given a set of activities with start and finish times, select
the largest number that don't overlap (the classic "how many meetings fit in one room"). The
correct greedy rule is surprising — always take the activity that FINISHES EARLIEST among those
still compatible. It's provably optimal. Two equally intuitive rules — take the earliest-starting,
or the shortest — are both wrong, and comparing them is the whole lesson: in greedy algorithms, the
criterion is everything.
"""


# region: earliest_finish
def schedule_earliest_finish(intervals):
    """The optimal greedy for interval scheduling: sort activities by FINISH time, then sweep
    left to right taking each activity whose start is not before the last taken finish. Finishing
    early leaves the most room for what follows — that's the intuition the exchange argument makes
    rigorous. O(n log n), dominated by the sort. Returns the chosen intervals."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[1]):   # by finish time
        if start >= last_finish:                 # compatible with everything chosen so far
            chosen.append((start, finish))
            last_finish = finish
    return chosen
# endregion


# region: wrong_greedies
def schedule_earliest_start(intervals):
    """A plausible-but-WRONG greedy: take the activity that starts earliest. One long early
    activity can block many short later ones, so this can badly underperform the optimum."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[0]):   # by start time
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen


def schedule_shortest(intervals):
    """Another plausible-but-WRONG greedy: take the shortest activity first. A short activity in
    the middle can conflict with two others that don't conflict with each other, losing one."""
    chosen = []
    taken = []
    for start, finish in sorted(intervals, key=lambda iv: iv[1] - iv[0]):   # by duration
        if all(finish <= s or start >= f for s, f in taken):        # overlaps nothing chosen
            taken.append((start, finish))
            chosen.append((start, finish))
    return chosen
# endregion

"""The reference and the contrast. There's no single 'library' for interval scheduling — it's a
classic exercise, not a stdlib call — so the reference here is a BRUTE-FORCE optimum: try every
subset of activities and keep the largest compatible one. It's O(2^n), usable only on small
instances, but it's the ground truth that proves the earliest-finish greedy is actually optimal
(and that the other greedies are not).

In production, the earliest-finish greedy IS what you'd ship — it's optimal and O(n log n). The
brute force exists only to verify it.
"""
from itertools import combinations


# region: brute_force
def optimal_brute_force(intervals):
    """The true maximum number of non-overlapping activities, by checking every subset from
    largest down. O(2^n) — only for verifying the greedy on small inputs. Returns a largest
    compatible subset."""
    def compatible(subset):
        s = sorted(subset, key=lambda iv: iv[0])
        return all(s[i][1] <= s[i + 1][0] for i in range(len(s) - 1))

    n = len(intervals)
    for size in range(n, 0, -1):
        for subset in combinations(intervals, size):
            if compatible(subset):
                return list(subset)
    return []
# endregion

Scratch vs library

The three greedy criteria differ by a single sort key, and one is optimal while the others aren't — that's the entire lesson of greedy algorithms compressed into one line of code. It reframes what "designing a greedy algorithm" means: the hard part isn't the sweep, which is trivial, but choosing and proving the criterion, which requires an exchange argument or a matroid structure. This is the paradigm's double edge — greedy is the simplest algorithm to write and the easiest to get subtly wrong, because a wrong criterion produces a working program with plausible output. The face-off's most important number isn't earliest-start's obvious 40% miss; it's shortest-first's 13.0-versus-13.1, a wrong algorithm that looks right on every test you'd casually run. The discipline greedy demands — prove it, don't benchmark it — is the real deliverable. The greedy algorithms you've already built (Dijkstra, Prim, Kruskal, Huffman) all came with such proofs, which is why they're correct; this chapter is where that proof obligation becomes explicit.

Where you'll actually meet it

Greedy algorithms run throughout systems and optimization. Data compression uses Huffman and related greedy codes. Network routing and spanning-tree protocols use Dijkstra and Prim/Kruskal. Operating-system and real-time schedulers use greedy rules (earliest-deadline-first, shortest-job-first) for task and CPU scheduling. Interval scheduling itself appears in room and resource booking, job shops, and register allocation in compilers. Greedy approximation algorithms tackle NP-hard problems — set cover for facility location and feature selection, greedy matching in ad auctions and assignment. Load balancers, cache-eviction policies (greedy LRU/LFU), and streaming algorithms lean on greedy choices. And in machine learning, greedy feature selection, decision-tree splitting (each node greedily picks the best split), and beam search are all this paradigm. Wherever a locally-best rule provably yields a global optimum — or a good-enough approximation — greedy is the tool.

Takeaways

A greedy algorithm makes the locally best choice at each step and never reconsiders, reaching a global optimum only when the problem has the greedy-choice property and optimal substructure — provable by an exchange argument or a matroid structure. Interval scheduling shows both the promise and the peril: the earliest-finish criterion is provably optimal (matching the brute-force maximum on every instance), while the equally intuitive earliest-start (40% worse) and shortest-first (usually near-optimal, but wrong on [0,10),[9,11),[10,20)) are not. The criterion is the algorithm, and it demands a proof, because a wrong greedy that's usually right is the most dangerous kind of bug.

The next chapter takes on the problems greedy can't solve: those with overlapping subproblems where no locally-best choice is safe. Dynamic programming handles them by considering all choices but remembering the answer to each subproblem so it's computed only once — turning the exponential blowup of naive recursion into polynomial time, and solving exactly the knapsack and shortest-path-with-choices problems where greedy gives no guarantee.