Greedy Algorithms: Take the Best Now, Then Prove It Is Safe

#Greedy in One Picture: The Big Idea

That is not automatic. If you walk uphill at every step, you reach a peak, but maybe not the tallest one. Some problems have only one peak, and greedy finds it. Others have many, and greedy gets stuck on a small one.

Here is the plan for the hour. First the two properties that make greedy safe. Then two ways to prove it. Then the classic problems, including two where greedy fails on purpose, and finally a guide for choosing between greedy and dynamic programming.

#Quick Recap: Sorting, Heaps and Dynamic Programming

Greedy solutions lean on three tools you already have.

1. Sorting puts items in the order a rule needs. Python's sorted costs O(n log n), and most greedy loops are that sort plus one pass (Sorting Algorithms).
2. A heap gives you the smallest item fast. heapq.heappush and heapq.heappop each cost O(log n) (Heaps).
3. Dynamic programming tries every choice and remembers sub-answers. It is the safe fallback when greedy is wrong (Recursion and DP).

#The Two Properties That Make Greedy Work

Two facts must both be true for a greedy rule to be correct.

So the pattern of every greedy proof is the same:

1. Pick a rule for the first choice.
2. Show that some best answer starts with that choice (greedy choice property).
3. Show that what remains is the same problem, smaller (optimal substructure).
4. Repeat. By induction, which means "if it holds for the first step and each step leaves the same situation, it holds all the way", the rule is right.

The hard part is step 2. The next two sections give you two tools for it.

#Proving a Greedy Right: The Exchange Argument

We use a problem you will solve in the next section. You have meetings with start and end times, one room, and you want to hold as many meetings as possible with no overlaps. The greedy rule: always pick the meeting that ends earliest. Here are the steps of the proof.

1. Let G be the meeting that ends earliest of all. Let O be any best schedule, listed in time order.
2. Look at O's first meeting, called F. If F is G, there is nothing to prove.
3. Otherwise, replace F with G in O. G ends no later than F ends, because G ends earliest of all.
4. F ended before O's second meeting began. G ends even earlier, so G also ends before the second meeting begins. Nothing clashes.
5. The new schedule holds the same number of meetings, so it is also a best schedule, and it starts with G.

So some best schedule starts with the greedy choice. That is the greedy choice property. Remove G and every meeting that clashes with it, and the rest is the same problem on fewer meetings, which is optimal substructure.

from itertools import combinations


def clash(a, b):
    return a[0] < b[1] and b[0] < a[1]


def valid(plan):
    return all(not clash(a, b) for a, b in combinations(plan, 2))


other = [(3, 5), (5, 7), (8, 11), (12, 16)]
swapped = [(1, 4)] + other[1:]
print(valid(other), valid(swapped), len(other), len(swapped))
# Output:
# True True 4 4

Both schedules are valid, and both hold 4 meetings. The swap cost nothing. Notice what the argument did not do: it never compared the greedy answer with every possible schedule. It argued about one step, and induction did the rest.

#The Stays Ahead Argument

For meetings, "ahead" means "finishes earlier". Let the greedy schedule end its meetings at times g1, g2, g3 and so on, and let any other valid schedule end its meetings at o1, o2, o3. The claim is that gk is at most ok, for every k.

1. For k = 1, greedy picks the earliest end of all, so g1 is at most o1.
2. Suppose gk is at most ok. The other schedule's next meeting starts after ok, so it also starts after gk.
3. So that same meeting is available to greedy after step k. Greedy picks the earliest-ending available meeting, so g(k+1) is at most o(k+1).
4. Therefore greedy is ahead at every step. Suppose greedy stopped after k meetings while the other schedule has more. Its meeting number k + 1 starts after ok, which is at least gk, so greedy could have taken it. That contradicts greedy stopping, so greedy has at least as many meetings.

On the example list, greedy ends its meetings at 4, 7, 11 and 16. The other schedule above ends at 5, 7, 11 and 16. Each greedy end is at most the matching one, as the argument says.

When do you use which? The exchange argument fits problems where you build one answer and can swap parts. Stays ahead fits problems where you walk along a line and compare progress, like "how far can I reach". Many proofs work with either.

#Interval Scheduling: Activity Selection

The right rule is the one we proved: earliest end first. It frees the room as soon as possible, so it leaves the most time for later meetings. Sort by end time. Walk through the list once. Keep a meeting if it starts at or after the end of the last kept meeting.

def max_activities(intervals):
    chosen = []
    last_end = float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen


meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(max_activities(meetings))
print(len(max_activities(meetings)))
# Output:
# [(1, 4), (5, 7), (8, 11), (12, 16)]
# 4

Time is O(n log n). The sort costs O(n log n) and the scan costs O(n), so the sort dominates. Extra space is O(n), for the sorted copy and the list of chosen meetings. The algorithm is greedy because it commits to each kept meeting and never reconsiders.

#Merging and Inserting Intervals

The trick is to sort by start. Then overlapping intervals sit next to each other. Keep a list of merged intervals. For each interval, if it starts at or before the end of the last merged one, stretch that one to the larger of the two ends. Otherwise start a new merged interval.

def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged


print(merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18], [17, 20]]))
print(merge_intervals([[1, 4], [4, 5]]))
print(merge_intervals([[1, 10], [2, 3], [4, 5]]))
# Output:
# [[1, 6], [8, 10], [15, 20]]
# [[1, 5]]
# [[1, 10]]

Inserting is easier. If the list is already sorted and has no overlaps, you can add one new interval in a single pass with no sort. There are three stages: copy every interval that ends before the new one starts, merge every interval that overlaps the new one, and copy the rest.

def insert_interval(intervals, new):
    result = []
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i])
        i += 1
    start, end = new
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    result.extend(intervals[i:])
    return result


print(insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
print(insert_interval([[1, 2], [3, 5]], [6, 9]))
# Output:
# [[1, 2], [3, 10], [12, 16]]
# [[1, 2], [3, 5], [6, 9]]

Time is O(n), because each interval is looked at once and the input is already sorted. Extra space is O(n) for the result.

#Fractional Knapsack Versus Zero-One Knapsack

You have a bag that holds up to 50 kilograms and three items. Each item has a value and a weight: 60 for 10 kg, 100 for 20 kg, and 120 for 30 kg. You want the most value in the bag.

The greedy rule is natural: take the item with the best value per kilogram first. The ratios are 6, 5 and 4. Before you run anything, predict what the rule gives when items cannot be split.

Now run all three: fractional greedy, zero-one greedy, and a brute-force check of every subset for the real best answer.

from itertools import combinations


def fractional_knapsack(items, capacity):
    total = 0.0
    for value, weight in sorted(items, key=lambda it: it[0] / it[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total


def greedy_zero_one(items, capacity):
    total = 0
    for value, weight in sorted(items, key=lambda it: it[0] / it[1], reverse=True):
        if weight <= capacity:
            total += value
            capacity -= weight
    return total


def best_zero_one(items, capacity):
    best = 0
    for size in range(len(items) + 1):
        for group in combinations(items, size):
            if sum(w for _, w in group) <= capacity:
                best = max(best, sum(v for v, _ in group))
    return best


items = [(60, 10), (100, 20), (120, 30)]
print(fractional_knapsack(items, 50))
print(greedy_zero_one(items, 50))
print(best_zero_one(items, 50))
# Output:
# 240.0
# 160
# 220

Here is what happened. With fractions allowed, greedy fills the bag with no waste and reaches 240, which is the true best. Without fractions, the best-ratio items leave 20 kg of the bag empty, and no remaining item fits in that gap. The real best leaves out the best-ratio item and takes the other two for 220.

Why is fractional knapsack safe? Exchange argument: if the best bag holds some low-ratio value while a better-ratio item is not fully taken, swap a little of the low one for the better one. The total value goes up or stays equal. Zero-one cannot swap "a little", so the argument breaks, and so does the algorithm.

#Coin Change: Canonical and Non-Canonical Coins

Back to the cashier. Given coin values and an amount, find the fewest coins that add up to the amount. The cashier's rule is greedy: take the biggest coin that fits, repeat.

def greedy_coins(coins, amount):
    used = []
    for coin in sorted(coins, reverse=True):
        count, amount = divmod(amount, coin)
        used.extend([coin] * count)
    return used if amount == 0 else None


def fewest_coins(coins, amount):
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and best[a - coin] + 1 < best[a]:
                best[a] = best[a - coin] + 1
    return best[amount] if best[amount] != float("inf") else None


for coins, amount in ([1, 3, 4], 6), ([1, 5, 10, 25], 63), ([1, 10, 25], 30):
    used = greedy_coins(coins, amount)
    print(coins, amount, used, len(used), fewest_coins(coins, amount))
# Output:
# [1, 3, 4] 6 [4, 1, 1] 3 2
# [1, 5, 10, 25] 63 [25, 25, 10, 1, 1, 1] 6 6
# [1, 10, 25] 30 [25, 1, 1, 1, 1, 1] 6 3

How do you know the cashier's coins are always fine? There is no one-line rule. You can prove it, or you can test: for every amount up to a limit, compare greedy with the dynamic programming answer. A known result says that if a coin set fails at all, it fails at some amount below the sum of its two largest coins. So the test only needs to look that far.

INF = float("inf")


def coin_table(coins, limit):
    best = [0] + [INF] * limit
    for a in range(1, limit + 1):
        for coin in coins:
            if coin <= a and best[a - coin] + 1 < best[a]:
                best[a] = best[a - coin] + 1
    return best


def first_failure(coins, limit):
    best = coin_table(coins, limit)
    for amount in range(1, limit + 1):
        used = greedy_coins(coins, amount)
        if (INF if used is None else len(used)) != best[amount]:
            return amount
    return None


print(first_failure([1, 5, 10, 25], 200))
print(first_failure([1, 2, 5, 10, 20, 50, 100], 500))
print(first_failure([1, 3, 4], 200))
print(first_failure([1, 5, 12], 200))
print(first_failure([1, 10, 25], 200))
# Output:
# None
# None
# 6
# 15
# 30

#Huffman Coding

Computers store text as bits. A plain code gives every letter the same number of bits. The word "abracadabra" has 5 different letters, so each needs 3 bits, and 11 letters cost 33 bits. But "a" appears 5 times and "c" appears once. Why pay the same for both?

The greedy idea builds a tree from the bottom. Treat each letter as a tiny tree with a count. Repeat: take the two trees with the smallest counts, join them under a new node whose count is their sum, and put it back. When one tree is left, read the codes: going left adds a 0, going right adds a 1. Rare letters end up deep, with long codes.

Hand trace for "abracadabra", whose counts are a 5, b 2, r 2, c 1, d 1:

Why is the greedy step safe? Exchange argument: in a best tree, the two rarest letters can always be swapped down to the deepest level as siblings without making the total longer, because swapping a rarer letter deeper and a commoner letter shallower can only help. So merging the two rarest first is safe.

import heapq


def build_tree(text):
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1
    heap = [(count, i, ch) for i, (ch, count) in enumerate(sorted(freq.items()))]
    heapq.heapify(heap)
    tie = len(heap)
    while len(heap) > 1:
        count1, _, left = heapq.heappop(heap)
        count2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (count1 + count2, tie, (left, right)))
        tie += 1
    return heap[0][2], freq


def make_codes(node, prefix="", codes=None):
    if codes is None:
        codes = {}
    if isinstance(node, str):
        codes[node] = prefix or "0"
    else:
        make_codes(node[0], prefix + "0", codes)
        make_codes(node[1], prefix + "1", codes)
    return codes


def decode(bits, tree):
    if isinstance(tree, str):
        return tree * len(bits)
    out, node = [], tree
    for bit in bits:
        node = node[int(bit)]
        if isinstance(node, str):
            out.append(node)
            node = tree
    return "".join(out)


text = "abracadabra"
tree, freq = build_tree(text)
codes = make_codes(tree)
bits = "".join(codes[ch] for ch in text)
print(freq)
print(codes)
print(bits, len(bits))
print(decode(bits, tree) == text, len(text) * 3)
# Output:
# {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
# {'a': '0', 'c': '100', 'd': '101', 'b': '110', 'r': '111'}
# 01101110100010101101110 23
# True 33

The text takes 23 bits instead of 33. The most common letter "a" got the one-bit code 0. Decoding walks the tree: follow each bit down, and when you land on a letter, write it and jump back to the root. That works only because the code is a prefix code.

Costs. Let L be the length of the text and n the number of different letters. Counting letters is O(L). Building the tree takes n - 1 merges, each with two pops and one push at O(log n), so O(n log n). Encoding and decoding each take time proportional to the number of bits. Extra space is O(n) for the heap and tree.

#Jump Game

You stand on cell 0 of a row. Each cell holds a number: the farthest you may jump forward from there. Can you reach the last cell?

def can_reach_end(jumps):
    farthest = 0
    for i, jump in enumerate(jumps):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True


print(can_reach_end([2, 3, 1, 1, 4]))
print(can_reach_end([3, 2, 1, 0, 4]))
print(can_reach_end([0]))
print(can_reach_end([0, 1]))
# Output:
# True
# False
# True
# False

#Gas Station

The brute force tries every start and simulates, which is O(n²). Two facts give a greedy answer in one pass.

Fact one: if the total gas is less than the total cost, no start works, since you can never get more than the stations hold.

Fact two: suppose you start at station s and your tank first goes below zero on the way to station j. Then no station between s and j works as a start either.

Pick one of them, called k. The drive from s to k only ever added a tank that was not negative. Starting at k skips that gain, so you reach j with even less gas and fail there too. So the next candidate is j + 1. Reset the tank and start again from there.

If the total is enough, the last candidate left standing is a valid start.

def start_station(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start


print(start_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
print(start_station([2, 3, 4], [3, 4, 3]))
# Output:
# 3
# -1

Time is O(n): the sum and the loop are each one pass. Extra space is O(1). A quadratic search became a linear one because one failure rules out a whole run of starting points at once. That pattern, "one failure eliminates many candidates", is typical of good greedy proofs.

#Minimum Meeting Rooms with a Heap

Now many meetings, and as many rooms as you need. How few rooms can hold them all? Two meetings that overlap need two rooms. A meeting that starts exactly when another ends can reuse that room.

import heapq


def min_rooms(meetings):
    ends = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)


print(min_rooms([(0, 30), (5, 10), (15, 20)]))
print(min_rooms([(7, 10), (2, 4)]))
print(min_rooms([(1, 5), (5, 8), (2, 6), (6, 9)]))
# Output:
# 2
# 1
# 2

#How to Find a Counterexample Fast

A greedy rule that works on your examples is not proven. The fastest way to doubt a rule is to try to break it by machine. Here is the recipe.

1. Write the rule in one sentence, such as "take the shortest meeting first".
2. Write a slow answer you trust: brute force over all subsets, or dynamic programming.
3. Generate every tiny input, say three intervals with ends from 0 to 7, and compare the rule with the slow answer on each.
4. Print the first input where they differ. That is your counterexample, and it is usually small enough to draw by hand.
5. If nothing differs on tiny inputs, try a bigger size or a nastier shape before you trust the rule. Even then, the next step is a proof.

Good shapes to try by hand: one big item that blocks many small ones, ties, and items that almost fit. Here is the recipe on three rules for activity selection. We skip inputs where the rule's sort key has ties, so the rule has no excuse.

from itertools import combinations


def clash(a, b):
    return a[0] < b[1] and b[0] < a[1]


def schedule_by(intervals, key):
    chosen = []
    for iv in sorted(intervals, key=key):
        if all(not clash(iv, c) for c in chosen):
            chosen.append(iv)
    return chosen


def best_count(intervals):
    for size in range(len(intervals), -1, -1):
        for group in combinations(intervals, size):
            if all(not clash(a, b) for a, b in combinations(group, 2)):
                return size


rules = {
    "earliest start": lambda iv: iv[0],
    "shortest first": lambda iv: iv[1] - iv[0],
    "earliest finish": lambda iv: iv[1],
}
all_ivs = [(s, e) for s in range(8) for e in range(s + 1, 8)]
for name, key in rules.items():
    found = None
    for trio in combinations(all_ivs, 3):
        if len({key(iv) for iv in trio}) < 3:
            continue
        if len(schedule_by(trio, key)) < best_count(trio):
            found = trio
            break
    if found is None:
        print(name, "no counterexample among three intervals")
    else:
        print(name, "fails on", found, "picks", len(schedule_by(found, key)), "best", best_count(found))
# Output:
# earliest start fails on ((0, 3), (1, 2), (2, 3)) picks 1 best 2
# shortest first fails on ((0, 3), (2, 4), (3, 7)) picks 1 best 2
# earliest finish no counterexample among three intervals

#Greedy or Dynamic Programming: A Decision Guide

Both methods split a problem into smaller choices. The difference is how they treat the choices that were not taken. Dynamic programming keeps every option alive and compares them. Greedy throws all but one away at once. So greedy is only legal when you can prove the discarded options were never better.

Ask these questions in order.

1. Can you name a single rule that picks the next choice? If not, you are not looking at greedy.
2. Can you swap that choice into any best answer without making it worse (exchange), or show it is never behind (stays ahead)? If yes, use greedy.
3. Do you find a counterexample on tiny inputs? If yes, the rule is wrong, so use dynamic programming or backtracking.
4. Cannot prove it and cannot break it? Write dynamic programming as the safe answer, and keep greedy as the fast guess that you test against it.

A short list of known cases:

#Where Greedy Shows Up in Real Systems

Huffman coding is a building block of well-known compression formats, including the DEFLATE method used by gzip and zip files, and the JPEG image format. The tree you built is the same idea.

Machine learning uses greedy choices in two places. A decision tree is grown by picking, at each node, the split that looks best right now, and it never revisits it. The result is good, but not guaranteed best.

The second place is text generation. When a language model writes text with greedy decoding, it picks the single most likely next token at each step. The most likely sentence as a whole can still be a different one. Beam search keeps several candidates instead, and so gets closer.

Scheduling tools, calendar apps, and operating systems use interval and heap logic like the meeting room code. Kruskal and Prim, which build a cheapest network, are greedy too.

When not to use greedy: whenever you cannot prove the rule, and whenever the problem has choices that interact in ways a single local score cannot see. The knapsack and coin sections show the symptom: an early choice that looks best uses up room a later choice needed.

#Common Mistakes

#Try It: The Five-Problem Ladder

Five problems, from easy to hard. Fill in each TODO and run. The output is the same every time. Stuck for fifteen minutes on a rung? Open the solution, read only that function, close it and rewrite it.

1. Merge intervals: sort by start, then stretch or start a new interval.
2. Jump game: keep one number, the farthest cell reachable.
3. Gas station: one pass, and reset the start after each failure.
4. Minimum meeting rooms: a heap of end times.
5. Counterexample hunt: find the smallest amount where greedy coin change uses too many coins.

Costs for the ladder, with reasons. Problem 1 is O(n log n) time, because of the sort, and O(n) space for the output. Problem 2 is O(n) time and O(1) space.

Problem 3 is O(n) time, two passes of one loop each, and O(1) space. Problem 4 is O(n log n) time, the sort plus n heap operations, and O(n) space. Problem 5 is O(limit * k log k) time, with k coin values: the table costs O(limit * k), and the solution sorts the coins again for each amount. Space is O(limit) for the table.

#Recap

A greedy algorithm makes the best-looking choice at each step and never undoes it. It is correct only when two things hold: the greedy choice is part of some best answer, and the rest is a smaller copy of the same problem. The exchange argument and the stays-ahead argument are the two ways to show it.

Earliest end first solves interval scheduling. Sorting by start and stretching ends merges intervals. Value per kilogram solves fractional knapsack but fails on zero-one knapsack. The largest-coin-first rule works for canonical coins and fails for others. Huffman coding merges the two rarest trees with a heap. Jump game, gas station and meeting rooms each reduce to one number or one heap.

When you doubt a rule, write a slow trusted answer and compare on tiny inputs. One counterexample ends the argument. If you can neither prove nor break a rule, dynamic programming is the safe choice.