Greedy Algorithms Explained: When Taking the Best Option Now Actually Works

A greedy algorithm makes the choice that looks best right now, commits to it, and never reconsiders. No backtracking, no lookahead, no table of subproblems. When it works, it collapses a problem that looks like it needs exponential search into a sort followed by a loop.

The catch is "when it works". Greedy is not a technique you apply; it is a claim you have to prove. Choose the wrong local rule and you get an algorithm that is fast, simple, produces answers that look completely reasonable, and is wrong on inputs you will never think to test. Most of this post is about that proof obligation. The worked example is activity selection — fitting the most bookings into one room — where three sort keys sound sensible and only one is correct. Then fractional knapsack, where greedy is provably optimal, next to 0/1 knapsack, where the identical rule throws away more than a quarter of the value.

The idea

Greedy is correct on a problem when two things hold. Both need stating precisely, because the vague versions are what lead people astray.

The greedy-choice property. There is at least one optimal solution that contains the choice your rule makes first. Note what that does not say. Not that the greedy choice looks good, or that it wins on average. Some optimal answer agrees with it. That is the licence to commit without regret.

Optimal substructure. After committing, what is left is a smaller instance of the same problem, and an optimal solution to that smaller instance combined with your choice is optimal overall.

Induction finishes the job: make the safe choice, shrink the problem, repeat. Every step keeps an optimal solution reachable.

In code this is nearly always the same shape: sort by a key, then make one pass keeping candidates that are still legal. The whole design problem is choosing the key, and the whole correctness problem is proving that key has the greedy-choice property. Two arguments do that. An exchange argument takes any optimal solution and shows you can swap greedy's choice into it without shrinking it, so an arbitrary optimal solution can be turned into greedy's. A "greedy stays ahead" argument compares the two step by step and shows greedy's partial answer is never behind on some measured quantity.

If you cannot produce one of those, you do not have a greedy algorithm. You have a heuristic — sometimes fine, but you should know which one you shipped.

Watching it work

One seminar room, seven booking requests with fixed start and finish times. You cannot move them and you cannot split them. Take as many as possible.

Two bookings clash when they overlap in time. Touching endpoints do not clash: one ending at 4 and one starting at 4 are fine, because the room is empty at that instant.

Seven requests give 128 subsets, so brute force is cheap here — but it is 2^n, and at 60 requests that is more subsets than there have been seconds since the Big Bang.

Three keys, two of them wrong

Shortest booking first. Short bookings use less of the room, so more should fit. It fails on 0-10, 9-11 and 10-20: the shortest is 9-11, and taking it blocks both of the others for a total of one, where 0-10 plus 10-20 gives two. A short booking placed badly straddles the boundary between two long ones and destroys both.

Earliest start first. Fill the room from the beginning of the day. It fails on 0-20, 1-5, 6-10 and 11-15: the earliest start occupies the whole day for one booking, where the other three fit together. When something starts tells you nothing about when it releases the room.

Earliest finish first. Take the booking that frees the room soonest, discard everything that clashes with it, repeat. This one is optimal, and it is the only one of the three that is.

The intuition fits in a sentence. The resource you are rationing is not time-slots, it is the moment the room becomes free again; every booking you accept pushes that moment forward, and earliest-finish pushes it forward as little as possible.

The scan

Sorted by finish time, the requests are B (4), F (5), C (6), D (7), A (9), E (10), G (11). Walk that list once, tracking the finish time of the last booking accepted.

• B (1 to 4) — nothing accepted yet, so take it. Room free from 4.
• F (3 to 5) — starts at 3, before 4. Clash, discard.
• C (0 to 6) — starts at 0. Clash, discard.
• D (5 to 7) — starts at 5, at or after 4. Take it. Room free from 7.
• A (3 to 9) — starts at 3, before 7. Clash, discard.
• E (6 to 10) — starts at 6, before 7. Clash, discard.
• G (8 to 11) — starts at 8, at or after 7. Take it. Room free from 11.

Three bookings: B, D, G. No four of these seven are pairwise clash-free, and the brute-force check further down verifies exactly that.

The code

The implementation is shorter than the explanation, which is normal for greedy.

def select_activities(activities: list[tuple[str, int, int]]) -> list[str]:
    """Pick the largest possible set of non-overlapping activities.

    Each activity is (name, start, finish). Sort by finish time, then walk
    the sorted list once, taking anything that starts at or after the
    finish time of the last activity taken.
    """
    chosen: list[str] = []
    last_finish: float = float("-inf")

    for name, start, finish in sorted(activities, key=lambda item: item[2]):
        # Compatible means it begins no earlier than the previous pick ended.
        # Touching endpoints are fine: the room frees up the moment it empties.
        if start >= last_finish:
            chosen.append(name)
            last_finish = finish

    return chosen


requests = [
    ("A", 3, 9), ("B", 1, 4), ("C", 0, 6), ("D", 5, 7),
    ("E", 6, 10), ("F", 3, 5), ("G", 8, 11),
]

print(select_activities(requests))
print(select_activities([]))
print(select_activities([("solo", 2, 3)]))

['B', 'D', 'G']
[]
['solo']

Now the two rules that fail. This scan takes the sort key as a parameter, so the only thing that changes between the runs is the key.

from collections.abc import Callable

Activity = tuple[str, int, int]


def select_greedy(activities: list[Activity],
                  key: Callable[[Activity], float]) -> list[str]:
    """Greedy interval scan with a swappable sort key.

    Sorts by `key`, then keeps every activity that clashes with nothing
    already chosen. The scan is identical each time; only the key changes.
    """
    chosen: list[Activity] = []

    for candidate in sorted(activities, key=key):
        _, start, finish = candidate
        # Two intervals clash unless one ends before the other begins.
        if all(finish <= other_start or start >= other_finish
               for _, other_start, other_finish in chosen):
            chosen.append(candidate)

    return [name for name, _, _ in sorted(chosen, key=lambda item: item[1])]


def duration(activity: Activity) -> int:
    return activity[2] - activity[1]


def start_time(activity: Activity) -> int:
    return activity[1]


def finish_time(activity: Activity) -> int:
    return activity[2]


duration_trap = [("X", 0, 10), ("Y", 9, 11), ("Z", 10, 20)]
start_trap = [("P", 0, 20), ("Q", 1, 5), ("R", 6, 10), ("S", 11, 15)]

print("shortest duration ->", select_greedy(duration_trap, duration))
print("earliest finish   ->", select_greedy(duration_trap, finish_time))
print("earliest start    ->", select_greedy(start_trap, start_time))
print("earliest finish   ->", select_greedy(start_trap, finish_time))

shortest duration -> ['Y']
earliest finish   -> ['X', 'Z']
earliest start    -> ['P']
earliest finish   -> ['Q', 'R', 'S']

Both wrong keys lose on four-element inputs. A greedy rule can be wrong on inputs that small and still look perfect on every example you happen to try, which suggests a habit: before trusting any greedy rule, write the exponential brute force and compare the two on a few hundred small random inputs.

from itertools import combinations
import random


def largest_compatible_set(activities: list[Activity]) -> int:
    """Size of the biggest clash-free subset, by trying every subset.

    Exponential and only useful as a reference answer to check greedy against.
    """
    in_start_order = sorted(activities, key=start_time)

    for size in range(len(in_start_order), 0, -1):
        for subset in combinations(in_start_order, size):
            # In start order, a subset is clash-free exactly when each
            # activity finishes no later than the next one starts.
            if all(before[2] <= after[1] for before, after in zip(subset, subset[1:])):
                return size
    return 0


random.seed(7)
trials: list[list[Activity]] = []
for _ in range(300):
    sample: list[Activity] = []
    for index in range(9):
        begins = random.randint(0, 24)
        sample.append((f"a{index}", begins, begins + random.randint(1, 9)))
    trials.append(sample)

agreed = sum(1 for sample in trials
             if len(select_activities(sample)) == largest_compatible_set(sample))
print(f"earliest-finish greedy was optimal on {agreed}/{len(trials)} random sets")

earliest-finish greedy was optimal on 300/300 random sets

Three hundred agreements is not a proof. It is exactly the evidence that would have stopped you shipping either of the broken keys.

How the code maps to the idea

sorted(activities, key=lambda item: item[2]) is the greedy rule; index 2 is the finish time. Everything else in the function is bookkeeping. This is the line you would have to change and re-prove if the problem changed.

last_finish is the shrunken subproblem. After accepting a booking that ends at time t, the rest of the problem is "select the most activities from those starting at or after t" — the same problem on a smaller set. Because the list is in finish order, one variable captures it and you never look back at what you took.

start >= last_finish is the compatibility test, and >= rather than > is a real decision, not a typo. It treats a booking as occupying [start, finish), so [1, 4) and [4, 7) do not overlap. If your domain says a meeting cannot start in a room that empties at that same instant, use > and nothing else changes. Getting this backwards is the most common bug in interval code.

float("-inf") removes the special case for the first activity, so there is no "if this is the first one" branch to get wrong. The remaining edge cases fall out too: an empty list never enters the loop and returns [], a single activity is always accepted, and ties in finish time need no tie-break, because either of two activities finishing at the same instant can start an optimal solution.

Why earliest finish is safe

Let A be the activity that finishes earliest in the whole set. Take any optimal solution O, list it in start order, and call its first activity X. Because A finishes earliest of everything, A finishes no later than X does.

Now replace X with A. The result is still clash-free: everything else in O starts at or after X finishes, and A finishes no later than X, so nothing in the rest of O can overlap A. One activity out, one in, so the set is the same size — still optimal, and it now contains A.

That is the greedy-choice property, proved. Delete A and everything clashing with it and you are left with the identical problem on a smaller set — optimal substructure. By induction, the greedy scan is optimal. The proof relies on nothing about the sizes of the activities or how they are distributed, which is what separates it from three hundred passing test cases.

Complexity

Time: O(n log n), dominated by the sort.

Any comparison sort of n items needs about n log n comparisons, and Python's sorted is Timsort, which is O(n log n) in the worst case. The log factor is a depth: you can only halve a range of n items about log 2 n times before the pieces are single elements, so each item takes part in roughly log 2 n merge steps.

The scan is linear. Each activity is visited exactly once, and each visit does one comparison plus at most one append and one assignment, all constant time. That is n comparisons and at most n appends, so O(n).

Total O(n log n) + O(n), and the larger term wins.

Best case: O(n), when the sort is free — activities that already arrive ordered by finish time, which happens naturally when you consume jobs as they complete.

Space: O(1) beyond the output. The scan holds one float and the result list. sorted builds a new list of n references, so the version above costs O(n); call activities.sort() to sort in place and the extra space is constant.

The brute force above is O(2^n) subsets. At n = 60, greedy does a few hundred comparisons; brute force does about 10^18 subset checks.

One caveat. Sorting once only works when the greedy key is fixed before you start. When the best remaining choice depends on what you have already taken — as in Dijkstra's algorithm, Prim's algorithm and Huffman coding — you need a priority queue that re-ranks candidates as you go, which is what heapq is for. The shape is still greedy; the "pick the best" step costs O(log n) per choice.

When to use it, and when not to

Use greedy when you can prove the greedy-choice property. That is the whole rule, and the rest of this section is about how sharp the boundary is.

Fractional knapsack: greedy is provably optimal

A 50 kg pack and three piles of ore, each with a total value and a total weight. The piles are divisible — you can take any fraction of one.

Item = tuple[str, int, int]  # name, total value, total weight


def value_density(item: Item) -> float:
    return item[1] / item[2]


def fractional_knapsack(items: list[Item],
                        capacity: int) -> tuple[float, list[tuple[str, float]]]:
    """Best value for a capacity when items can be split into any fraction."""
    remaining = capacity
    total = 0.0
    plan: list[tuple[str, float]] = []

    for name, value, weight in sorted(items, key=value_density, reverse=True):
        if remaining == 0:
            break
        # Take the whole item, or whatever fraction of it still fits.
        taken = min(weight, remaining)
        total += value * taken / weight
        plan.append((name, taken / weight))
        remaining -= taken

    return total, plan


ore = [("dust", 60, 10), ("flakes", 100, 20), ("nuggets", 120, 30)]

for name, value, weight in ore:
    print(f"{name:8} value {value:3}  weight {weight:2}  value/kg {value / weight:.1f}")

best_value, plan = fractional_knapsack(ore, 50)
print(f"fractional greedy scores {best_value:.0f}")
for name, fraction in plan:
    print(f"  {name:8} {fraction:.0%}")

dust     value  60  weight 10  value/kg 6.0
flakes   value 100  weight 20  value/kg 5.0
nuggets  value 120  weight 30  value/kg 4.0
fractional greedy scores 240
  dust     100%
  flakes   100%
  nuggets  67%

The exchange argument works again, and divisibility is what makes it work. Suppose an optimal packing contains a kilogram of a lower-density pile while a kilogram of a higher-density pile is still on the ground. Swap them. The weight is unchanged, so the pack is still legal, and the value went up — contradicting optimality. So an optimal pack consumes the piles in density order, which is what the code does.

0/1 knapsack: the same rule falls apart

Remove one word from the problem. The ore now comes in sealed crates: take the whole crate or none of it.

def zero_one_greedy(items: list[Item], capacity: int) -> tuple[int, list[str]]:
    """The same density-first rule, but nothing may be cut. Not optimal."""
    remaining = capacity
    total = 0
    taken: list[str] = []

    for name, value, weight in sorted(items, key=value_density, reverse=True):
        if weight <= remaining:
            taken.append(name)
            total += value
            remaining -= weight

    return total, taken


def zero_one_best(items: list[Item], capacity: int) -> tuple[int, list[str]]:
    """Exhaustive search over all subsets, as a reference answer."""
    best_total, best_set = 0, []

    for size in range(len(items) + 1):
        for subset in combinations(items, size):
            if sum(item[2] for item in subset) <= capacity:
                total = sum(item[1] for item in subset)
                if total > best_total:
                    best_total, best_set = total, [item[0] for item in subset]

    return best_total, best_set


print("0/1 greedy: ", zero_one_greedy(ore, 50))
print("0/1 optimal:", zero_one_best(ore, 50))

0/1 greedy:  (160, ['dust', 'flakes'])
0/1 optimal: (220, ['flakes', 'nuggets'])

Identical rule, identical data, 27 percent of the value gone. The swap step in the proof moved a kilogram; with sealed crates the smallest movable thing is a whole crate, and moving a crate changes the total weight, so the swapped packing may not even fit. The proof does not get harder — it stops being true.

The fix is dynamic programming, which considers taking and not taking each crate and keeps both branches alive in a table. That is the standard escape route: when the greedy choice is not provably safe, stop committing to it and let 0/1 knapsack explore both options.

The same trap has a smaller, more famous instance. Paying an amount with the largest coin that fits is greedy, and it is correct for the coin systems most currencies use — but not for all of them.

def greedy_coins(coins: list[int], amount: int) -> list[int]:
    """Pay an amount by always reaching for the largest coin that fits."""
    picked: list[int] = []

    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            picked.append(coin)
            amount -= coin

    return picked


print(greedy_coins([1, 5, 10, 25], 30), "- optimal is [25, 5]")
print(greedy_coins([1, 3, 4], 6), "- optimal is [3, 3]")

[25, 5] - optimal is [25, 5]
[4, 1, 1] - optimal is [3, 3]

With US coins greedy is optimal for every amount. With coins of 1, 3 and 4 it needs three coins to make 6 where two suffice. Greedy's correctness was never a property of the algorithm; it was a property of the coin system, and nothing warned you when you crossed the line. Coin change covers the DP that is correct for any system.

Matroids, honestly

There is real theory here. A matroid is a family of "independent" sets with two properties: every subset of an independent set is independent, and whenever one independent set is bigger than another, some element of the bigger one can be moved into the smaller one keeping it independent. The Rado-Edmonds theorem says that for any matroid, sorting elements by weight and greedily keeping whatever preserves independence yields the maximum-weight independent set. Kruskal's algorithm is exactly that theorem on the graphic matroid, where independent means "contains no cycle".

The caveat is that matroids explain some greedy algorithms, not all. Activity selection is not a matroid: take [0, 10) as one independent set and the pair [0, 1), [2, 3) as another — the pair is bigger, yet neither of its members can join the first set without clashing, so the exchange property fails. Treat matroid theory as a powerful special case that tells you when greedy is guaranteed, not a test you can run on every problem.

Where it shows up in the real world

Huffman coding, inside DEFLATE — so inside gzip, zlib, PNG and every ZIP file — is greedy: repeatedly merge the two least frequent symbols into one node. That provably produces an optimal prefix code, by an exchange argument on the two deepest leaves. JPEG's entropy coding stage uses Huffman codes too.

Minimum spanning trees. Kruskal's algorithm sorts every edge by weight and adds each one that does not close a cycle; Prim's grows a single tree by repeatedly adding the cheapest edge leaving it. Both are provably optimal, and both underpin network design and clustering — running Kruskal and stopping early is single-linkage hierarchical clustering.

Dijkstra's algorithm settles the closest unvisited node at every step and never revisits it. That greedy choice is safe only because edge weights are non-negative; allow negative weights and you need Bellman-Ford instead. The OSPF and IS-IS routing protocols run Dijkstra to compute forwarding tables.

Interval partitioning. Activity selection maximises bookings for one room; the sibling problem asks for the fewest rooms that fit all the bookings. Sort by start time and keep a min-heap of the rooms' finish times, reusing a room whenever its earliest finish has passed. The room count it produces provably equals the largest number of bookings overlapping at any single instant.

Real-time scheduling. Earliest Deadline First — always run the task whose deadline is soonest — is greedy and provably optimal for preemptive single-processor scheduling: if any schedule can meet all the deadlines, EDF does. Linux implements it in the SCHED_DEADLINE scheduling class.

Common mistakes

Assuming greedy works because your examples pass. Both broken keys above match brute force on plenty of inputs. Write the exponential reference implementation and compare on a few hundred small random cases before you believe the rule.

Picking the intuitive key rather than the safe one. "Shortest first" is the natural guess and it is wrong. The key that works is usually the one that optimises the resource constraining future choices — here, the moment the room comes free — not the one that looks locally efficient.

Forgetting to sort, or sorting the wrong way round. A greedy scan over unsorted input is just an arbitrary feasible answer. Density-ordered knapsack needs reverse=True; finish-ordered activity selection does not.

Getting the endpoint comparison wrong. start >= last_finish treats intervals as half-open and lets a booking begin exactly when the previous one ends; start > last_finish forces a gap. Both are legitimate, and picking the one your domain does not mean is a bug that only shows up on touching intervals.

Reconsidering earlier choices. An algorithm that goes back and un-takes something is not greedy — it is local search or backtracking, with different complexity and different correctness conditions. Greedy's speed comes entirely from never revisiting.

Practice

1. Given a list of intervals, return the minimum number of them to delete so the rest have no overlap. Solve it with one call to the activity selection scan.
2. Interval partitioning: given all the bookings, find the fewest rooms that hold them, using heapq to track room finish times.
3. Given jobs each with a duration and a deadline, order them to minimise the maximum lateness, and check earliest-deadline-first against brute force on eight jobs.
4. Change the fractional knapsack so every pile has the same value per kilogram, then explain why any order is now optimal and the exchange proof still holds.
5. Search every coin system of the form 1, a, b with a and b under 20 and report the smallest amount where greedy uses more coins than the optimum.

Summary

Greedy algorithms are the cheapest correct answer to a small set of problems and a confident wrong answer to everything else. The code is never the hard part — activity selection is a sort and a five-line loop. The hard part is the exchange argument showing the local choice is safe, and the discipline to notice when a small change to the problem, like sealing the ore into crates, quietly destroys it.

Test every greedy rule against brute force on small inputs before you trust it, and be suspicious of any rule you cannot justify in three sentences.

Keep reading

• The 0/1 Knapsack Problem — what to do when greedy fails and you need the full table.
• Dynamic Programming — the technique that handles the problems greedy cannot.
• Big O Notation — the counting arguments behind the bounds used above.