Greedy Algorithms

Activity Selection

Given a set of activities, each with a start and end time, and a single resource that can only handle one activity at a time, schedule as many non-overlapping activities as possible. The greedy rule: always sort by earliest finish time, and greedily take an activity whenever it starts at or after the last one taken ends. Sorting by finish time (not start time, and not duration) is what makes this work, finishing early leaves the most room for everything that comes after.

def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    # activities: list of (start, end) pairs
    sorted_by_end = sorted(activities, key=lambda a: a[1])
    selected = [sorted_by_end[0]]
    last_end = sorted_by_end[0][1]
    for start, end in sorted_by_end[1:]:
        if start >= last_end:          # this activity doesn't overlap the last one taken
            selected.append((start, end))
            last_end = end
    return selected

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
              (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(activity_selection(activities))

[(1, 4), (5, 7), (8, 11), (12, 16)]

Laid out on a timeline, sorted top to bottom by finish time, the greedy rule almost reads itself: scan down, take the first bar, then keep taking the next bar that starts at or after the last one you took ended. The four green bars never overlap, and no larger non-overlapping set exists:

Fractional Knapsack

Given items with a value and a weight, and a knapsack with limited capacity, maximize total value, but this time items can be split into fractions (think bulk grain, not individual gold bars). The greedy rule: sort by value-to-weight ratio, take as much of the best-ratio item as the remaining capacity allows, then move to the next best ratio.

def fractional_knapsack(items: list[tuple[float, float]], capacity: float) -> float:
    # items: list of (value, weight) pairs
    items_sorted = sorted(items, key=lambda item: item[0] / item[1], reverse=True)
    total_value = 0.0
    remaining = capacity
    for value, weight in items_sorted:
        if remaining <= 0:
            break
        take = min(weight, remaining)           # take the whole item, or just a fraction
        total_value += value * (take / weight)
        remaining -= take
    return total_value

# (value, weight) pairs; capacity 50
items = [(60, 10), (100, 20), (120, 30)]
print(fractional_knapsack(items, 50))

240.0

Because any item can be split, there's never a reason to leave capacity unused while a higher-ratio item is still available, so filling greedily by ratio is always at least as good as any other order. That guarantee depends entirely on fractional items: Lesson 19's 0/1 knapsack removes the ability to split items, and that single constraint is enough to break this greedy strategy completely.

Coin Change: Where Greedy Can Quietly Fail

Make a target amount using the fewest coins from a set of denominations. The greedy rule: always take the largest coin that still fits. With familiar denominations like US coins, this works perfectly:

def greedy_coin_change(amount: int, denominations: list[int]) -> list[int] | None:
    coins = []
    remaining = amount
    for coin in sorted(denominations, reverse=True):
        while remaining >= coin:
            coins.append(coin)
            remaining -= coin
    return coins if remaining == 0 else None

print(greedy_coin_change(41, [25, 10, 5, 1]))

[25, 10, 5, 1]

Four coins for 41 cents, and that really is the minimum possible. But greedy's success here comes from US coin denominations being unusually well-behaved, not from anything fundamental about coin change. Swap in denominations [1, 3, 4] and ask for 6:

print(greedy_coin_change(6, [4, 3, 1]))

[4, 1, 1]

Recognizing When Greedy Is Safe to Use

The pattern across the examples above: greedy is only provably correct when a problem has what's called the greedy-choice property, a locally optimal first step is always part of some globally optimal solution, so committing to it early never rules out reaching the best answer. Activity selection and fractional knapsack both have this property, and it can be proven with an exchange argument like the one above. Coin change with arbitrary denominations doesn't have it, the best first coin sometimes leads only to worse total solutions. Two graph algorithms coming up in Lesson 20, Dijkstra's shortest path and Kruskal's/Prim's minimum spanning tree, are also greedy algorithms that happen to have this property, which is exactly why they're correct without needing dynamic programming's exhaustive approach.

Complexity at a Glance

The O(n log n) cost in the first two rows is entirely the sort, once the items are ordered, the greedy pass itself is a single O(n) sweep. Coin change's greedy pass is O(amount) in the worst case (repeatedly subtracting the largest coin), fast, but only trustworthy for denomination sets that are specifically known to be well-behaved.