Greedy Algorithms: When the Locally Best Choice Works and How to Prove It

By 0xmote · May 25, 2026 · 17 min read · Updated Sep 27, 2026 Intermediate Tutorial

Key takeaways

A greedy algorithm commits to the choice that looks best right now and never revisits it. That is only correct when an exchange argument shows some optimal solution starts with the same choice. This guide proves interval scheduling, shows exactly where greedy breaks (coins {1,3,4}, 0/1 knapsack, sort-by-start), and gives a brute-force stress test that catches a wrong greedy before the judge does.

Introduction

A greedy algorithm builds a solution one decision at a time, takes whichever option looks best at that moment, and never undoes it. Because nothing is revisited, greedy solutions are usually a sort followed by a single pass: O(n log n) time and very little code.

The catch is that “looks best right now” is only safe for some problems. For others the same style of code produces an answer that is plausible, passes the sample tests and is wrong. The skill is not writing the loop; it is knowing which key to sort by and being able to argue why the first choice cannot hurt you. This article works through that argument on the standard problems, then shows the cases where it fails and what to use instead.

What Makes a Greedy Algorithm Correct

Two properties have to hold together.

Greedy-choice property. There is an optimal solution that contains the greedy first choice. You do not need every optimal solution to contain it, only one.

Optimal substructure. After making that choice, what remains is a smaller instance of the same problem, and an optimal answer to the remainder plus the greedy choice is optimal overall.

Dynamic programming also relies on optimal substructure. The difference is the first property: DP does not know which first choice is right, so it tries all of them and caches the results. Greedy claims it already knows. That claim is what you have to prove.

The usual proof tool is an exchange argument:

Take an arbitrary optimal solution OPT.
If OPT’s first choice differs from the greedy choice, swap the greedy choice in.
Show the swapped solution is still valid and no worse.
Therefore an optimal solution starting with the greedy choice exists; repeat on the remainder.

If you cannot complete step 3, that is often a sign that a counterexample exists, and it is worth looking for one before writing code.

Interval Scheduling: The Canonical Proof

Problem: given meetings as (start, end), choose the maximum number that do not overlap. A meeting may start exactly when the previous one ends (Baekjoon 1931 uses this rule).

def max_meetings(meetings):
    # Sort by end time; break ties by start time so zero-length
    # meetings like (2, 2) come after (1, 2).
    order = sorted(meetings, key=lambda m: (m[1], m[0]))
    last_end = float('-inf')
    chosen = []
    for start, end in order:
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

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

Why earliest end time is safe

Let g be the meeting with the smallest end time, and let OPT be any maximum schedule whose first meeting is o. By the choice of g, end(g) <= end(o). Every other meeting in OPT starts at or after end(o), hence at or after end(g). Replacing o with g therefore creates no overlap and keeps the same count. So a maximum schedule starting with g exists. Remove g and every meeting that starts before end(g), and the rest is the same problem on fewer meetings.

Notice what the proof uses: only that g ends first. That is why the other intuitive keys have no such proof, and why they fail.

Keys that look reasonable and fail

def pick(meetings, key):
    order = sorted(meetings, key=key)
    chosen = []
    for s, e in order:
        if all(e <= cs or s >= ce for cs, ce in chosen):
            chosen.append((s, e))
    return len(chosen)

# Earliest start: one long meeting blocks three short ones
m1 = [(0, 10), (1, 2), (3, 4), (5, 6)]
print(pick(m1, key=lambda m: m[0]))          # 1  (optimal is 3)

# Shortest duration: a short meeting straddles two compatible ones
m2 = [(0, 5), (4, 7), (6, 11)]
print(pick(m2, key=lambda m: m[1] - m[0]))   # 1  (optimal is 2)

The tie-breaking bug

The tie-break in max_meetings is not decoration. With zero-length meetings allowed, sorting by end time alone can place (2, 2) before (1, 2):

def by_end_only(meetings):
    order = sorted(meetings, key=lambda m: m[1])
    count, last_end = 0, float('-inf')
    for s, e in order:
        if s >= last_end:
            count += 1
            last_end = e
    return count

print(by_end_only([(2, 2), (1, 2)]))        # 1
print(len(max_meetings([(2, 2), (1, 2)])))  # 2

Python’s sort is stable, so the result depends on input order, which is exactly the kind of bug that passes the samples. This one cost me a wrong answer on Baekjoon 1931 the first time I solved it: I had the proof right and the sort key wrong, and I spent longer staring at the loop than at the one-character difference in the key.

Variants that reuse the same proof

LeetCode 435 (Non-overlapping Intervals) asks for the minimum number of intervals to remove. That is n - (maximum you can keep), so it is the same algorithm:

def erase_overlap_intervals(intervals):
    kept = 0
    last_end = float('-inf')
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

print(erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]))  # 1
print(erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]))          # 2

Recognizing “minimum removals” as “maximum kept” is a common step: the greedy argument is usually cleaner on the maximization side.

Where Greedy Fails

Coin change with a non-canonical system

With coins {500, 100, 50, 10}, taking the largest coin first is optimal. With {1, 3, 4} it is not:

def greedy_coins(coins, amount):
    count = 0
    for coin in sorted(coins, reverse=True):
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1

def dp_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(greedy_coins([500, 100, 50, 10], 1260))            # 6
print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))  # 3 2

Greedy takes 4 + 1 + 1; the optimum is 3 + 3. The exchange argument breaks at step 3: swapping in a 4 does not let you rebuild the rest with fewer coins, because the leftover 2 cannot be made from 3s.

A coin system where greedy is always optimal is called canonical. If every coin divides the next larger one (1, 10, 50, 100, 500 in multiples), the system is canonical, but that condition is sufficient, not necessary: US coins {1, 5, 10, 25} are canonical even though 10 does not divide 25. For a system you do not know, there is a practical check. For systems that include a 1 coin, Kozen and Zaks showed that if a counterexample exists, the smallest one is below the sum of the two largest coins, so a finite scan is enough:

def first_counterexample(coins):
    coins = sorted(coins)
    if len(coins) < 2:
        return None
    limit = coins[-1] + coins[-2]
    for x in range(1, limit):
        if greedy_coins(coins, x) != dp_coins(coins, x):
            return x
    return None

for system in ([1, 5, 10, 25], [1, 3, 4], [1, 7, 10], [1, 2, 5, 10, 20, 50]):
    print(system, first_counterexample(system))
# [1, 5, 10, 25] None
# [1, 3, 4] 6
# [1, 7, 10] 14
# [1, 2, 5, 10, 20, 50] None

Without a 1 coin, greedy can also fail to find any answer at all: greedy_coins([5, 3], 9) returns -1 after taking a 5, while dp_coins([5, 3], 9) returns 3 (3 + 3 + 3). The DP itself is covered in Dynamic Programming: Memoization vs Tabulation, including how to reconstruct which coins were used.

Fractional knapsack vs 0/1 knapsack

Both problems ask for maximum value under a weight limit. In the fractional version you may take part of an item; in the 0/1 version you take all of it or none.

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

def greedy_01_by_ratio(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 knapsack_01(items, capacity):
    dp = [0] * (capacity + 1)
    for value, weight in items:
        for w in range(capacity, weight - 1, -1):
            dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[capacity]

items = [(60, 10), (100, 20), (120, 30)]  # (value, weight)
print(fractional_knapsack(items, 50))  # 240.0
print(greedy_01_by_ratio(items, 50))   # 160
print(knapsack_01(items, 50))          # 220

The ratios are 6, 5 and 4 per unit. For the fractional version the exchange argument goes through: any unit of capacity spent on a lower-ratio item can be traded for a unit of a higher-ratio item that is not fully taken, and value can only go up. For 0/1, the greedy takes the 10 and 20 items and then cannot fit the 30, leaving 20 units of capacity wasted. Taking 20 + 30 fills the knapsack exactly for 220. Indivisibility is what breaks the swap, and it is why 0/1 knapsack needs DP (the loop order in knapsack_01 is explained in DP Patterns).

A general rule I use: if the problem lets earlier choices constrain later ones in a way that depends on exact amounts (remaining capacity, remaining sum), be suspicious of greedy. If the constraint is only “what comes after this point in a sorted order”, greedy is more likely to work.

Greedy With a Stack: Removing Digits

Problem (Programmers “Create the Largest Number”): remove exactly k digits from a number string to make the largest possible number, keeping the order of the remaining digits.

The leftmost digit matters most. If a digit is followed by a larger one, removing the smaller digit always improves the result, because the larger one moves one place left. A stack keeps the digits chosen so far in non-increasing order; each new digit pops smaller digits while removals remain.

def largest_after_removing(number, k):
    stack = []
    for digit in number:
        while k and stack and stack[-1] < digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    if k:
        stack = stack[:-k]  # digits are non-increasing; drop from the end
    return ''.join(stack)

print(largest_after_removing("1924", 2))        # 94
print(largest_after_removing("1231234", 3))     # 3234
print(largest_after_removing("4177252841", 4))  # 775841
print(largest_after_removing("9876", 2))        # 98

The if k: guard matters. stack[:-k] with k == 0 is stack[:0], the empty list, so an unguarded slice silently returns "" whenever every removal happened inside the loop:

print([1, 2, 3][:-0])  # []

The input "9876" exercises the other branch: nothing is ever popped because the digits already decrease, so all removals come from the tail.

The mirror problem, LeetCode 402 (Remove K Digits), asks for the smallest number. Flip the comparison and strip leading zeros:

def smallest_after_removing(num, k):
    stack = []
    for digit in num:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    if k:
        stack = stack[:-k]
    return ''.join(stack).lstrip('0') or '0'

print(smallest_after_removing("1432219", 3))  # 1219
print(smallest_after_removing("10200", 1))    # 200
print(smallest_after_removing("10", 2))       # 0

Each digit is pushed and popped at most once, so both run in O(n). The monotonic-stack mechanics are the same ones covered in Stacks and Queues.

Greedy by Sorting Two Sequences: Assign Cookies

Problem (LeetCode 455): child i is satisfied by a cookie of size at least greed[i]; each child gets at most one cookie. Maximize satisfied children.

def assign_cookies(greed, cookies):
    greed = sorted(greed)
    cookies = sorted(cookies)
    child = 0
    for size in cookies:
        if child < len(greed) and size >= greed[child]:
            child += 1
    return child

print(assign_cookies([1, 2, 3], [1, 1]))  # 1
print(assign_cookies([1, 2], [1, 2, 3]))  # 2

The exchange argument: the least greedy child should get the smallest cookie that satisfies them. If an optimal assignment gives that child a larger cookie, swap it with whatever smaller sufficient cookie it used elsewhere (or left unused); the other child still gets a cookie at least as large as before. Cookies too small for the least greedy child are too small for everyone and can be skipped. Sorting both lists turns this into a two-pointer walk, which is the pattern in Two Pointers.

Greedy With a Heap: Cheapest Merge Order

Problem: you have piles of sizes s1, s2, .... Merging two piles costs their combined size. Find the minimum total cost to merge everything into one pile (Baekjoon 1715, and the same structure as Huffman coding).

import heapq

def min_merge_cost(sizes):
    heap = list(sizes)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        total += a + b
        heapq.heappush(heap, a + b)
    return total

print(min_merge_cost([10, 20, 40]))  # 100
print(min_merge_cost([4, 3, 2, 6]))  # 29

A pile’s size is paid once for every merge it participates in, so small piles should be merged first and sit deepest in the merge tree. The standard Huffman proof is an exchange argument: in some optimal tree, the two smallest piles are siblings at the deepest level, because swapping a deeper large pile with a shallower small pile cannot increase the cost.

The trap here is sorting once instead of using a heap. After merging 10 and 20 into 30, the new pile has to compete with the remaining piles again; a single sorted pass would merge in the wrong order whenever a merged pile becomes larger than the next unmerged one.

A Constraint Detail: Gym Clothes

The Programmers problem “Gym Clothes” is a small greedy with a data trap. Students with a spare may lend to an immediate neighbor; students who lost their clothes but brought a spare use their own spare and cannot lend.

def gym_clothes(n, lost, reserve):
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)
    for r in sorted(reserve_set):
        if r - 1 in lost_set:       # lend to the lower neighbor first
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)
    return n - len(lost_set)

print(gym_clothes(5, [2, 4], [1, 3, 5]))  # 5
print(gym_clothes(3, [1, 2], [2, 3]))     # 2

Scanning lenders in increasing order and preferring the lower neighbor is safe: the lower neighbor can only be served by this lender or the one below it, which has already been processed, while the upper neighbor may still be reached by the next lender. Forgetting the set subtraction is the actual bug people submit. Without it, student 2 in the second test lends a spare they need themselves, and the function returns 3.

Testing a Greedy Before You Trust It

In a contest or interview you rarely have time for a formal proof, but you almost always have time for a stress test. Write the obvious exponential solution, run both on small random inputs, and stop at the first mismatch:

import random
from itertools import combinations

def brute_force(meetings):
    for size in range(len(meetings), 0, -1):
        for subset in combinations(meetings, size):
            ordered = sorted(subset, key=lambda m: (m[1], m[0]))
            if all(ordered[i][1] <= ordered[i + 1][0] for i in range(size - 1)):
                return size
    return 0

def greedy(meetings, key):
    count, last_end = 0, float('-inf')
    for s, e in sorted(meetings, key=key):
        if s >= last_end:
            count += 1
            last_end = e
    return count

def stress(key, trials=2000, seed=1):
    rng = random.Random(seed)
    for _ in range(trials):
        n = rng.randint(1, 6)
        meetings = []
        for _ in range(n):
            s = rng.randint(0, 8)
            meetings.append((s, s + rng.randint(0, 4)))
        if greedy(meetings, key) != brute_force(meetings):
            return meetings
    return None

print(stress(key=lambda m: (m[1], m[0])))  # None
print(stress(key=lambda m: m[1] - m[0]))   # [(0, 3), (4, 5), (1, 3), (0, 0), (0, 4)]
print(stress(key=lambda m: m[0]))          # [(7, 10), (3, 3), (7, 7), (6, 9)]

Keep the value range small (here 0 to 12) so that ties and touching endpoints show up often; those are where greedy keys break. A mismatch on five meetings is something you can trace by hand in a minute.

The failure I recognize most in my own practice is convincing myself with the sample input plus two cases I invented. Hand-made cases tend to be “nice”: distinct endpoints, no ties, no zero-length items. The random generator does not share my assumptions, and it has turned up a counterexample to an idea I was sure of more than once. Now I run a stress test whenever the greedy key is something I came up with rather than a known result.

Common Reasons a Greedy Submission Fails

Wrong sort key. Earliest start or shortest length for interval scheduling; value instead of value per weight for fractional knapsack.
Missing tie-break. Equal end times with zero-length intervals; equal ratios where the problem cares about weight.
Custom order expressed as a key that is not a total order. LeetCode 179 (Largest Number) needs “a before b if a+b > b+a”. A plain reverse string sort gives the wrong answer:

from functools import cmp_to_key

def largest_number(nums):
    strs = [str(n) for n in nums]
    def compare(a, b):
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0
    strs.sort(key=cmp_to_key(compare))
    result = ''.join(strs)
    return '0' if result[0] == '0' else result

print(largest_number([3, 30, 34, 5, 9]))                     # 9534330
print(largest_number([0, 0]))                                # 0
print(''.join(sorted(['3', '30', '34', '5', '9'], reverse=True)))  # 9534303

Using greedy where amounts interact. Arbitrary coin systems, 0/1 knapsack, subset sums. If a counterexample exists, switch to DP.
Sorting once when the candidates change. Merge costs, task scheduling, and anything where a processed item produces a new candidate need a heap.
Edge-case slicing and empty inputs. stack[:-0], an empty interval list, k equal to the length of the string.

Which greedy choices are safe

Problem	Greedy choice	Why it is safe (or not)
Interval scheduling	Earliest end time	Exchange: the earliest-ending meeting can replace OPT’s first meeting
Fractional knapsack	Highest value per weight	Capacity can be traded unit by unit
0/1 knapsack	(none)	Items are indivisible; ratio greedy gets 160 vs 220 in the example
Coin change, canonical systems	Largest coin first	Holds for {1,5,10,25}; check unknown systems with a finite scan
Coin change, {1,3,4}	(none)	6 = 3+3 beats 4+1+1
Remove k digits	Pop smaller (or larger) predecessors	Leftmost digit dominates the comparison
Merge piles	Two smallest first, via heap	Huffman exchange argument

When greedy fails, the fix is almost always to consider every choice at each step and cache results, which is dynamic programming. DP Patterns covers the knapsack and coin-counting forms of that.