When greedy works: proofs and counterexamples

A greedy algorithm builds its answer one decision at a time and never takes a decision back: pay with the largest coin that fits, grant the booking that ends first, repair the quickest phone next. The code is short and usually runs in O(n log n), one sort and one scan. Greedy is correct when the locally best choice always belongs to some best answer, and what is left after it is a smaller copy of the same problem. Many rules that sound right fail that test: largest coin first pays 6 with coins of 1, 3 and 4 as 4 + 1 + 1, three coins, where 3 + 3 needs two.

So settle a greedy idea in two moves. First try to break it with a brute force on small inputs, which finds a counterexample quickly when one exists. If nothing breaks, prove it, usually with an exchange argument or a stays-ahead argument. This lesson breaks two plausible rules with measured failure counts, proves earliest end first for bookings both ways with programs that carry out each proof, and solves one problem in full, the order of repairs that keeps customers waiting least, in five languages.

When a greedy rule is safe

NIST’s Dictionary of Algorithms and Data Structures defines a greedy algorithm as one that always takes the best immediate choice, which finds the overall optimum for some problems and falls short on others. Most greedy solutions in coding rounds share one shape: order the candidates by a key, scan them once, and take each candidate that still fits. Only the key changes: the end of a booking, the length of a job, the value of a coin. Two properties make a rule safe:

• The greedy choice belongs to some best answer. At least one best answer starts with greedy’s choice; it need not be every best answer.
• What is left is the same problem, smaller. After the choice, the rest of a best answer is a best answer to what remains: the bookings that start after the first one ends, or the amount still to pay.

When both hold, induction finishes the proof. Coin change shows the first property failing: to pay 6 with coins of 1, 3 and 4, largest first takes the 4, but no best payment contains a 4, because the only two-coin payment is 3 + 3.

Intuition is a poor judge of the first property, because every plausible rule looks safe on the examples that suggested it. For bookings of one machine, earliest start first grants [8, 17) before [9, 11) and [11, 13), one request where two fit, and shortest first grants [4, 6), which overlaps both [0, 5) and [5, 10). Earliest end first gets both right, and the proofs below show that it always does. A coding round needs that kind of evidence: a counterexample that sinks a rule, or a proof that none exists.

Guess, break, prove

Treat every greedy idea as a claim to test, in this order:

1. State the rule exactly, ties included. “Shortest first” is not a rule until it says which of two equal lengths goes first, and ties are often where rules break.
2. Try to break it. Run a brute force that tries every answer beside the greedy, on every small input or on thousands of random ones from a fixed seed. The stress-testing harness does exactly this, with a brute force from the lesson on brute force to optimal as the judge. Small inputs are enough: every counterexample in this lesson has two or three items.
3. If a counterexample turns up, keep the smallest. It shows which choice went wrong and points to the next step: a different key, or dynamic programming, which tries both ways of a choice instead of committing to one.
4. If none turns up, prove it. A clean stress test makes a proof likely, not certain: a rule can fail only on inputs larger than the test tried.

The two usual proofs, which the lecture slides for Kleinberg and Tardos’s Algorithm Design call the exchange argument and “greedy algorithm stays ahead”, work in opposite directions:

Breaking a rule: largest coin first

Pay an amount exactly with as few coins as possible, using as many coins of each value as you like. Largest coin first takes the largest coin that is not more than what is left, again and again. Try one case by hand before the brute force: what does it pick for 12 with coins of 1, 6 and 10?

"""Largest coin first, for 12 with coins of 1, 6 and 10. Work out what it picks before you look at the output."""


def greedy(coins, amount):
    """The coins that largest-first picks for amount, or None if it is left with a remainder it cannot pay."""
    picked = []
    for coin in sorted(coins, reverse=True):
        while coin <= amount:
            picked.append(coin)
            amount -= coin
    return picked if amount == 0 else None


print(greedy([1, 6, 10], 12))

[10, 1, 1]

It takes the 10 and then two 1s, three coins, where 6 + 6 needs two. A case found by hand is luck; a brute force finds every case. Below, fewest() computes the fewest coins for every amount from 0 upwards, building each amount from smaller ones, which is dynamic programming in its simplest form. The program compares greedy with it, amount by amount:

"""Largest coin first: for each coin system, the first amount it pays with more coins than it needs.

Each amount up to the two largest coins added together is compared with the fewest coins possible, which the
function fewest() finds by building on smaller amounts. For a system that contains a 1, an amount where greedy goes
wrong, if there is one, always turns up in that range (the bound of Kozen and Zaks), so "none" settles the system.
"""


def greedy(coins, amount):
    """The coins that largest-first picks for amount, or None if it is left with a remainder it cannot pay."""
    picked = []
    for coin in sorted(coins, reverse=True):
        while coin <= amount:
            picked.append(coin)
            amount -= coin
    return picked if amount == 0 else None


def fewest(coins, limit):
    """best[x] is a shortest list of coins adding up to x (None if no list does), for every x from 0 to limit."""
    best = [[]] + [None] * limit
    for x in range(1, limit + 1):
        for coin in coins:
            rest = best[x - coin] if coin <= x else None
            if rest is not None and (best[x] is None or len(rest) + 1 < len(best[x])):
                best[x] = sorted(rest + [coin], reverse=True)
    return best


def first_failure(coins):
    """(limit, amount, greedy's coins, the fewest coins) for the first amount where greedy needs more coins."""
    largest, second = sorted(coins)[-1], sorted(coins)[-2]
    limit = largest + second
    best = fewest(coins, limit)
    for amount in range(1, limit + 1):
        mine = greedy(coins, amount)
        if best[amount] is not None and (mine is None or len(mine) > len(best[amount])):
            return limit, amount, mine, best[amount]
    return limit, None, None, None


def show(picked):
    """[30, 1, 1, 1] as "30 + 3 × 1": a coin used three times or more is shown with its count."""
    parts = []
    for coin in sorted(set(picked), reverse=True):
        count = picked.count(coin)
        parts += [f"{count} × {coin}"] if count >= 3 else [str(coin)] * count
    return " + ".join(parts)


SYSTEMS = [[1, 2, 5, 10, 20, 50], [1, 3, 4], [1, 5, 10, 25], [1, 10, 25], [1, 4, 5], [1, 29, 30]]

for coins in SYSTEMS:
    limit, amount, mine, best = first_failure(coins)
    print(f"coins {', '.join(map(str, coins))} (amounts 1 to {limit} checked)")
    if amount is None:
        print("  greedy pays every amount with the fewest coins")
    else:
        print(f"  first failure at {amount}: greedy pays {show(mine)} ({len(mine)} coins), the fewest is {show(best)} ({len(best)})")

coins 1, 2, 5, 10, 20, 50 (amounts 1 to 70 checked)
  greedy pays every amount with the fewest coins
coins 1, 3, 4 (amounts 1 to 7 checked)
  first failure at 6: greedy pays 4 + 1 + 1 (3 coins), the fewest is 3 + 3 (2)
coins 1, 5, 10, 25 (amounts 1 to 35 checked)
  greedy pays every amount with the fewest coins
coins 1, 10, 25 (amounts 1 to 35 checked)
  first failure at 30: greedy pays 25 + 5 × 1 (6 coins), the fewest is 3 × 10 (3)
coins 1, 4, 5 (amounts 1 to 9 checked)
  first failure at 8: greedy pays 5 + 3 × 1 (4 coins), the fewest is 4 + 4 (2)
coins 1, 29, 30 (amounts 1 to 59 checked)
  first failure at 58: greedy pays 30 + 28 × 1 (29 coins), the fewest is 29 + 29 (2)

Two of the six systems never go wrong: 1, 2, 5, 10, 20, 50 and 1, 5, 10, 25. The other four fail, and not always early. With coins of 1, 29 and 30, greedy is right for every amount up to 57, then pays 58 with a 30 and twenty-eight 1s: 29 coins, where 29 + 29 needs 2.

How far must a check go? Kozen and Zaks proved that if largest first fails at all for a coin system with a 1 coin, its first failure is no larger than the two largest coins added together, which is why the program stops at that sum. Pearson later gave a test that takes about k³ steps for k coin values; the paper by Adamaszek and Niewiarowska in the references sums up both results. How often does largest first fail? This program checks every system with coins up to 30, with three, four and five values, and searches past the bound, up to three times the largest coin:

"""How many coin systems does largest-coin-first get wrong? Every system of three, four or five coin values that
contains a 1 and has no coin above 30.

Each system is checked far past the bound, up to three times its largest coin, to see where its first failure falls:
above its largest coin (so checking small amounts only would miss it), and never above the two largest added together.
"""
from itertools import combinations

TOP = 30


def greedy_count(coins_high_to_low, amount):
    """How many coins largest-first uses, or None if it is left with a remainder (cannot happen with a 1 coin)."""
    used = 0
    for coin in coins_high_to_low:
        used += amount // coin
        amount %= coin
    return used if amount == 0 else None


def first_failure(coins, limit):
    """The smallest amount up to limit that greedy pays with more coins than necessary, or None."""
    high_to_low = sorted(coins, reverse=True)
    fewest = [0] * (limit + 1)
    for amount in range(1, limit + 1):
        fewest[amount] = 1 + min(fewest[amount - c] for c in coins if c <= amount)
        if greedy_count(high_to_low, amount) > fewest[amount]:
            return amount
    return None


for size in (3, 4, 5):
    systems = failing = above_largest = above_bound = 0
    latest = None
    for rest in combinations(range(2, TOP + 1), size - 1):
        coins = (1, *rest)
        systems += 1
        amount = first_failure(coins, 3 * coins[-1])
        if amount is None:
            continue
        failing += 1
        above_largest += amount > coins[-1]
        above_bound += amount > coins[-1] + coins[-2]
        if latest is None or amount > latest[1]:
            latest = (coins, amount)
    print(f"{size} coins, the largest at most {TOP}: {systems:,} systems")
    print(f"  greedy fails somewhere in {failing:,} of them ({failing / systems:.0%})")
    print(f"  the first failure is above the largest coin in {above_largest:,} of those, above the two largest added together in {above_bound}")
    print(f"  the latest first failure: {latest[1]}, for coins {', '.join(map(str, latest[0]))}")

3 coins, the largest at most 30: 406 systems
  greedy fails somewhere in 260 of them (64%)
  the first failure is above the largest coin in 260 of those, above the two largest added together in 0
  the latest first failure: 58, for coins 1, 29, 30
4 coins, the largest at most 30: 3,654 systems
  greedy fails somewhere in 3,262 of them (89%)
  the first failure is above the largest coin in 2,338 of those, above the two largest added together in 0
  the latest first failure: 58, for coins 1, 2, 29, 30
5 coins, the largest at most 30: 23,751 systems
  greedy fails somewhere in 23,069 of them (97%)
  the first failure is above the largest coin in 11,157 of those, above the two largest added together in 0
  the latest first failure: 58, for coins 1, 2, 3, 29, 30

Most coin systems you could invent fail: 64 % of the three-coin systems, 89 % of the four-coin ones and 97 % of the five-coin ones. Every three-coin system that fails does so first above its largest coin, so checking only the amounts below the largest coin would have found nothing, and none of the 27,811 systems first failed above the bound. The habit to take into a round: never accept largest first because it works on the examples. Check every amount up to the bound, which takes a dozen lines and a fraction of a second.

Breaking a rule: the 0/1 knapsack

A bag holds at most C kilograms. Each item has a weight and a value and goes in whole or not at all. Three rules come to mind for the most valuable load: the most valuable item first, the lightest first, or the best value per kilogram first, each putting in every item that still fits. The program runs all three on 10,000 random bags, each able to hold half the weight of its items, and compares them with the best load, found by trying every subset:

"""Three greedy rules for a 0/1 knapsack, each against the best load found by trying every subset of items.

A bag holds at most `capacity` kilograms. Each item has a weight and a value and goes in whole or not at all. Each
rule sorts the items by its own key and puts every item that still fits into the bag.
"""
import random
from itertools import combinations

RULES = {
    "most valuable first": lambda item: -item[1],
    "lightest first": lambda item: item[0],
    "best value per kg first": lambda item: -item[1] / item[0],
}


def greedy_value(items, capacity, key):
    room, value = capacity, 0
    for weight, worth in sorted(items, key=key):
        if weight <= room:
            room -= weight
            value += worth
    return value


def best_value(items, capacity):
    """The most valuable load, by trying all 2 ** len(items) subsets."""
    best = 0
    for size in range(1, len(items) + 1):
        for chosen in combinations(items, size):
            if sum(w for w, _ in chosen) <= capacity:
                best = max(best, sum(v for _, v in chosen))
    return best


rng = random.Random(27)
TRIALS = 10_000
wrong = dict.fromkeys(RULES, 0)
worst = dict.fromkeys(RULES, 1.0)
for _ in range(TRIALS):
    items = [(rng.randint(1, 10), rng.randint(1, 20)) for _ in range(rng.randint(3, 6))]
    capacity = sum(w for w, _ in items) // 2
    best = best_value(items, capacity)
    for name, key in RULES.items():
        got = greedy_value(items, capacity, key)
        if got < best:
            wrong[name] += 1
            worst[name] = min(worst[name], got / best)

print(f"{TRIALS:,} random bags of 3 to 6 items, each bag holding half their weight: how often each rule misses")
for name in RULES:
    print(f"  {name:<24} wrong in {wrong[name]:>5,} ({wrong[name] / TRIALS:5.1%}), at worst {worst[name]:.0%} of the best value")

# The smallest bag that defeats value per kg, with no two items of the same value per kg (so no tie decides it):
# the fewest kilograms of capacity first, then the lightest items.
for capacity in range(1, 10):
    found = None
    for items in combinations([(w, v) for w in range(1, capacity + 1) for v in range(1, 10)], 2):
        (w1, v1), (w2, v2) = items
        if v1 * w2 == v2 * w1:
            continue
        if greedy_value(items, capacity, RULES["best value per kg first"]) < best_value(items, capacity):
            found = items
            break
    if found:
        break
print(f"smallest bag that value per kg gets wrong: capacity {capacity} kg, items {found} as (kg, value)")
print(f"  value per kg loads {greedy_value(found, capacity, RULES['best value per kg first'])}, the best load is worth {best_value(found, capacity)}")

10,000 random bags of 3 to 6 items, each bag holding half their weight: how often each rule misses
  most valuable first      wrong in 1,082 (10.8%), at worst 35% of the best value
  lightest first           wrong in 5,568 (55.7%), at worst 5% of the best value
  best value per kg first  wrong in 1,939 (19.4%), at worst 15% of the best value
smallest bag that value per kg gets wrong: capacity 2 kg, items ((1, 2), (2, 3)) as (kg, value)
  value per kg loads 2, the best load is worth 3

All three go wrong, and often. Value per kilogram, the rule that sounds cleverest, misses the best load in 19.4 % of the bags, and once it collects only 15 % of the best value. The smallest bag that defeats it holds 2 kg: a 1 kg item worth 2 goes in first, at 2 per kilogram against 1.5, and then the 2 kg item worth 3 no longer fits. Give the second item W kilograms and a value of W + 1 in a bag of W kilograms, and the rule still collects 2: as small a share of the best as you like.

The same rule is optimal when items can be cut. In the fractional knapsack, where rice or sugar can be taken by the kilogram, taking as much as possible of the material worth most per kilogram, then of the next, gives the optimum, as NIST’s dictionary states. An exchange shows why: if a load holds some of a cheaper material while part of a dearer one is left out, moving a kilogram from the cheaper to the dearer raises the value, so a best load has no such pair, and that is the greedy load. With whole items that move is not allowed, and the step where a proof breaks is usually where a counterexample lives. The decision version of the 0/1 problem is NP-complete, NIST’s dictionary notes, so no fast rule of this kind is known to solve it; the dynamic-programming modules of this track solve it for whole-number weights by trying both choices, in or out, for each item.

Proving a rule: the exchange argument

A makerspace has one laser cutter and eight requests for it, each a span of hours [start, end): a request holds the cutter from its start up to, but not including, its end, so one may start in the hour another ends. Grant as many requests as possible with no two overlapping. The rule is earliest end first: sort the requests by end time and grant each one that starts no earlier than the end of the last request granted. “Ending early leaves the most time for the rest” is an intuition, not a proof. The exchange argument turns it into one in three steps:

1. Line them up. Write greedy’s grants in time order, g₁, g₂, …, gₘ, and any best schedule in time order, o₁, o₂, …, oₖ.
2. Swap at the first difference. Suppose the two agree up to position i − 1 and differ at position i. Greedy chose gᵢ as the request that ends earliest among those that start no earlier than the end of gᵢ₋₁, and oᵢ is one of those, so gᵢ ends no later than oᵢ. Put gᵢ in place of oᵢ in the best schedule. It starts no earlier than the end of oᵢ₋₁ = gᵢ₋₁, and it ends no later than oᵢ did, so it still ends by the time oᵢ₊₁ starts: the schedule is still valid and still has k requests.
3. Repeat, then count. Each swap makes the best schedule agree with greedy’s in one more position. If greedy had granted fewer than k requests, after m swaps the best schedule would be g₁ … gₘ followed by oₘ₊₁, a request that starts no earlier than the end of gₘ, and greedy would have granted it. So greedy grants at least k requests, and since no valid schedule has more than k, its schedule is a best one.

This program carries out the argument on the eight requests. It takes a best schedule, found by trying all 256 subsets, and swaps greedy’s choices into it one at a time, checking after every swap that the schedule is still valid and just as long:

"""An exchange argument, carried out: an optimal schedule is turned into the greedy one, one swap at a time.

Requests for a makerspace's laser cutter, as [start, end) in hours: a request holds the cutter from its start up to,
but not including, its end, so one may start at the hour another ends. The goal is to grant as many as possible.
"""
from itertools import combinations

REQUESTS = {"P": (8, 10), "Q": (9, 11), "R": (10, 12), "S": (11, 13), "T": (12, 15), "U": (13, 14), "V": (14, 17), "W": (15, 16)}


def valid(names):
    """True when no two of the requests overlap (names in time order)."""
    times = sorted(REQUESTS[n] for n in names)
    return all(earlier[1] <= later[0] for earlier, later in zip(times, times[1:]))


def in_time_order(names):
    return sorted(names, key=lambda n: REQUESTS[n])


def earliest_end_first():
    granted, free_from = [], 0
    for name in sorted(REQUESTS, key=lambda n: REQUESTS[n][1]):
        start, end = REQUESTS[name]
        if start >= free_from:
            granted.append(name)
            free_from = end
    return granted


def an_optimal_schedule():
    """The largest valid set of requests, by trying all 2 ** 8 subsets; among those, the one that ends latest."""
    for size in range(len(REQUESTS), 0, -1):
        found = [c for c in combinations(REQUESTS, size) if valid(c)]
        if found:
            return in_time_order(max(found, key=lambda c: sum(REQUESTS[n][1] for n in c)))
    return []


def show(names):
    return " ".join(f"{n}[{REQUESTS[n][0]}, {REQUESTS[n][1]})" for n in names)


greedy = earliest_end_first()
other = an_optimal_schedule()
print(f"greedy, earliest end first: {show(greedy)}")
print(f"an optimal schedule:        {show(other)}")
step = 0
while other != greedy:
    k = next(i for i in range(len(other)) if other[i] != greedy[i])
    step += 1
    old = other[k]
    other = other[:k] + [greedy[k]] + other[k + 1:]
    assert valid(other), "an exchange must keep the schedule valid"
    print(f"swap {step}: at position {k + 1}, {old} (ends {REQUESTS[old][1]}) becomes {greedy[k]} (ends {REQUESTS[greedy[k]][1]})")
    print(f"        {show(other)}: still {len(other)} requests, none overlapping")
print("the optimal schedule is now the greedy one, and it never lost a request")

greedy, earliest end first: P[8, 10) R[10, 12) U[13, 14) W[15, 16)
an optimal schedule:        Q[9, 11) S[11, 13) U[13, 14) V[14, 17)
swap 1: at position 1, Q (ends 11) becomes P (ends 10)
        P[8, 10) S[11, 13) U[13, 14) V[14, 17): still 4 requests, none overlapping
swap 2: at position 2, S (ends 13) becomes R (ends 12)
        P[8, 10) R[10, 12) U[13, 14) V[14, 17): still 4 requests, none overlapping
swap 3: at position 4, V (ends 17) becomes W (ends 16)
        P[8, 10) R[10, 12) U[13, 14) W[15, 16): still 4 requests, none overlapping
the optimal schedule is now the greedy one, and it never lost a request

Three swaps turn Q S U V into P R U W, and the schedule never loses a request or gains an overlap. That is the whole shape of an exchange argument: take a best answer that differs from greedy’s, change it at the first difference to greedy’s choice, and show that the change keeps it valid and no worse. In an interview, say the second step aloud: the swap, and the reason it is safe, are what the interviewer listens for.

Proving a rule: greedy stays ahead

The same rule has a second proof, which compares instead of editing. Choose a measure for partial answers, here the hour at which the k-th granted request ends. The claim: for every k, greedy’s k-th request ends no later than the k-th request of any valid schedule, a best one or not.

• For k = 1 the claim holds, because greedy’s first request is the one that ends earliest of all.
• If it holds for k − 1, the other schedule’s k-th request starts no earlier than the end of its own (k − 1)-th, which is no earlier than the end of greedy’s (k − 1)-th. So that request was still open to greedy when it made its k-th choice, and greedy took one that ends no later.

Staying ahead gives the count at once. If another schedule had more requests than greedy’s m, its (m + 1)-th request would start no earlier than the end of its m-th, so no earlier than the end of greedy’s m-th, and greedy would have granted it. The program shows the claim on the laser cutter, then checks it against every valid schedule of 2,000 random sets of requests:

"""Greedy stays ahead: the k-th request that earliest-end-first grants never ends later than the k-th request of any
other valid schedule. Shown on the laser-cutter requests, then checked against every valid schedule of 2,000 random
sets of requests.
"""
import random
from itertools import combinations

CUTTER = {"P": (8, 10), "Q": (9, 11), "R": (10, 12), "S": (11, 13), "T": (12, 15), "U": (13, 14), "V": (14, 17), "W": (15, 16)}


def earliest_end_first(requests):
    """The requests (start, end) that greedy grants, in the order it grants them."""
    granted, free_from = [], 0
    for start, end in sorted(requests, key=lambda r: r[1]):
        if start >= free_from:
            granted.append((start, end))
            free_from = end
    return granted


def valid_schedules(requests):
    """Every set of requests with no two overlapping, each in time order."""
    for size in range(1, len(requests) + 1):
        for chosen in combinations(sorted(requests), size):
            if all(a[1] <= b[0] for a, b in zip(chosen, chosen[1:])):
                yield list(chosen)


name = {times: n for n, times in CUTTER.items()}
greedy = earliest_end_first(CUTTER.values())
other = [CUTTER[n] for n in "QSUV"]
print("k   greedy (P R U W)   the other (Q S U V)")
for k, (mine, theirs) in enumerate(zip(greedy, other), start=1):
    print(f"{k}   {name[mine]} ends at {mine[1]:<6}   {name[theirs]} ends at {theirs[1]}")

rng = random.Random(4)
compared = behind = longer = schedules = 0
for _ in range(2000):
    requests = []
    for _ in range(rng.randint(1, 7)):
        start = rng.randint(0, 20)
        requests.append((start, start + rng.randint(1, 6)))
    greedy = earliest_end_first(requests)
    for schedule in valid_schedules(requests):
        schedules += 1
        longer += len(schedule) > len(greedy)
        for k in range(min(len(schedule), len(greedy))):
            compared += 1
            behind += greedy[k][1] > schedule[k][1]
print(f"2,000 random sets of requests: {schedules:,} valid schedules, {compared:,} k-th requests compared")
print(f"greedy's k-th request ended later in {behind} of them, and {longer} schedules had more requests than greedy")

k   greedy (P R U W)   the other (Q S U V)
1   P ends at 10       Q ends at 11
2   R ends at 12       S ends at 13
3   U ends at 14       U ends at 14
4   W ends at 16       V ends at 17
2,000 random sets of requests: 31,114 valid schedules, 68,054 k-th requests compared
greedy's k-th request ended later in 0 of them, and 0 schedules had more requests than greedy

Greedy is ahead or level in every row, and in 68,054 comparisons it was never behind. A check like this is not a proof, but it catches a wrong induction cheaply before you write it down. Stays ahead suits answers built step by step with a natural score after each step; the exchange argument suits orders, and sets you can edit one item at a time. A third style, a bound that every answer must respect and greedy meets, comes up with the fewest-rooms problem later in this module.

A problem solved in full: the repair queue

This section solves one easy problem in the order a coding round asks for it: the brute force, what to notice, the greedy rule, why it is optimal, a dry run, code in five languages, a stress test and the edge cases.

Five inputs serve as examples, and every version of the code below runs them:

1. [7, 2, 4] gives 21. Repaired in the order 2, 4, 7, the phones are ready at minutes 2, 6 and 13, and 2 + 6 + 13 = 21. In the order given they would be ready at 7, 9 and 13, a total of 29.
2. [5] gives 5: one customer, who waits for one repair.
3. [3, 3, 3] gives 18 in every order: 3 + 6 + 9.
4. [12, 3, 7, 3, 20, 1, 9, 5] gives 171, where the order given costs 280.
5. 200,000 phones of 10,000 minutes each give 200,001,000,000,000, the largest total the limits allow, far beyond the 2,147,483,647 that a 32-bit integer holds.

The brute force: every order

Try every order and keep the smallest total. It is right by construction, which makes it the judge for the fast version, but n phones have n! orders:

"""The brute force for the repair queue: try every order of the repairs and keep the smallest total wait."""
from itertools import permutations
from math import factorial


def total_wait(minutes):
    """Each customer waits from opening until their phone is ready: add up the moments the repairs finish."""
    clock = total = 0
    for m in minutes:
        clock += m
        total += clock
    return total


def least_total(minutes):
    """(the smallest total, an order that reaches it), over all len(minutes)! orders."""
    return min((total_wait(order), list(order)) for order in permutations(minutes))


for queue in ([7, 2, 4], [5], [3, 3, 3], [12, 3, 7, 3, 20, 1, 9, 5]):
    total, order = least_total(queue)
    tried = factorial(len(queue))
    print(f"{queue}: {tried:,} order{'s' if tried > 1 else ''} tried, the least total is {total}, for {order}")
    print(f"  in the order given the total is {total_wait(queue)}")
for n in (10, 15, 20):
    print(f"{n} phones: {factorial(n):,} orders to try")

[7, 2, 4]: 6 orders tried, the least total is 21, for [2, 4, 7]
  in the order given the total is 29
[5]: 1 order tried, the least total is 5, for [5]
  in the order given the total is 5
[3, 3, 3]: 6 orders tried, the least total is 18, for [3, 3, 3]
  in the order given the total is 18
[12, 3, 7, 3, 20, 1, 9, 5]: 40,320 orders tried, the least total is 171, for [1, 3, 3, 5, 7, 9, 12, 20]
  in the order given the total is 280
10 phones: 3,628,800 orders to try
15 phones: 1,307,674,368,000 orders to try
20 phones: 2,432,902,008,176,640,000 orders to try

Eight phones already need 40,320 orders, and 20 phones would need about 2.4 × 10¹⁸, far more than any time limit allows. At the limits of the problem the brute force is useful only as a judge on small inputs.

What to notice

Look at two neighbours in any order: a repair of a minutes directly before a repair of b minutes, with S minutes of work before both. Swapping them affects only these two customers. Everyone before them is ready at the same moment as before, and so is everyone after them, because the pair takes a + b minutes in either order. Before the swap the two are ready at S + a and S + a + b; after it, at S + b and S + a + b. The total changes by b − a, so whenever a longer repair sits directly before a shorter one, swapping them lowers the total by the difference.

Shortest repair first

Sort the repairs from shortest to longest, then walk through them with a clock: add each repair’s minutes to the clock, and the clock to the total. That is one sort and one scan, O(n log n) time, with O(n) extra memory for the sorted copy. A second way to see it: the repair in position p, counting from 1, delays every customer from position p to the end, so its minutes are counted n − p + 1 times, and sorting puts the shortest repairs where they count most.

Why it is optimal

The proof is an exchange argument with neighbours. Some order has the smallest total, because there are only finitely many orders; call it a best order. If it had a longer repair directly before a shorter one, swapping the two would lower the total by their difference, which is more than 0, so the order would not be best. A best order therefore has no such pair, and an order with no such pair is sorted from shortest to longest. Ties do not matter: every sorted order is the same list of lengths, with the same total. So the sorted order is a best order, and shortest repair first is optimal.

A dry run

The first half of this trace replays the argument on [7, 2, 4], swapping neighbours until no longer repair sits before a shorter one. The second half is the greedy scan, one row per phone:

"""The repair queue [7, 2, 4], twice: swaps that put a shorter repair first, then the greedy pass, step by step."""


def total_wait(minutes):
    clock = total = 0
    for m in minutes:
        clock += m
        total += clock
    return total


order = [7, 2, 4]
print(f"the order given {order}: total {total_wait(order)}")
swapped = True
while swapped:
    swapped = False
    for i in range(len(order) - 1):
        if order[i] > order[i + 1]:
            before = total_wait(order)
            longer, shorter = order[i], order[i + 1]
            order[i], order[i + 1] = shorter, longer
            print(f"swap {longer} and {shorter}: {order}, total {total_wait(order)}, which is {before - total_wait(order)} less ({longer} - {shorter})")
            swapped = True
print("no repair is followed by a shorter one now: the order is sorted")
print()
print("shortest repair first, one row per phone")
print("repair   ready at   total so far")
clock = total = 0
for m in sorted([7, 2, 4]):
    clock += m
    total += clock
    print(f"{m:>6}   {clock:>8}   {total:>12}")

the order given [7, 2, 4]: total 29
swap 7 and 2: [2, 7, 4], total 24, which is 5 less (7 - 2)
swap 7 and 4: [2, 4, 7], total 21, which is 3 less (7 - 4)
no repair is followed by a shorter one now: the order is sorted

shortest repair first, one row per phone
repair   ready at   total so far
     2          2              2
     4          6              8
     7         13             21

The two swaps lower the total by 5 and then by 3, the differences of the repairs they swap, from 29 to 21. The scan reaches the same 21 without trying anything: the clock reads 2, 6 and 13 as the phones are ready, and the total adds those moments up.

The code in five languages

The same function in Python, JavaScript, Java, C++ and Go. Run runs the Python and JavaScript versions in your browser:

"""The repair queue: the smallest total waiting time is reached by repairing the shortest jobs first."""


def least_total_wait(minutes):
    """Sum, over all customers, of the minutes from opening until their phone is ready, in the best order."""
    clock = total = 0
    for m in sorted(minutes):  # sorted() leaves the caller's list as it was
        clock += m  # the moment this phone is ready
        total += clock
    return total


print(least_total_wait([7, 2, 4]))
print(least_total_wait([5]))
print(least_total_wait([3, 3, 3]))
print(least_total_wait([12, 3, 7, 3, 20, 1, 9, 5]))
print(least_total_wait([10_000] * 200_000))  # the largest input the limits allow

21
5
18
171
200001000000000

// The repair queue: the smallest total waiting time is reached by repairing the shortest jobs first.

function leastTotalWait(minutes) {
  // A sorted copy, with a comparison: sort() on its own compares numbers as text, so 10000 would come before 2.
  const order = [...minutes].sort((a, b) => a - b);
  let clock = 0;
  let total = 0; // at most 2.00001e14 here, far below Number.MAX_SAFE_INTEGER (about 9.007e15): exact
  for (const m of order) {
    clock += m; // the moment this phone is ready
    total += clock;
  }
  return total;
}

console.log(leastTotalWait([7, 2, 4]));
console.log(leastTotalWait([5]));
console.log(leastTotalWait([3, 3, 3]));
console.log(leastTotalWait([12, 3, 7, 3, 20, 1, 9, 5]));
console.log(leastTotalWait(new Array(200_000).fill(10_000))); // the largest input the limits allow

21
5
18
171
200001000000000

import java.util.Arrays;

// The repair queue: the smallest total waiting time is reached by repairing the shortest jobs first.
public class Waiting {
    static long leastTotalWait(int[] minutes) {
        int[] order = minutes.clone(); // sort a copy, not the caller's array
        Arrays.sort(order);
        long clock = 0, total = 0; // long: the total reaches 2.00001e14, far above the 2,147,483,647 an int holds
        for (int m : order) {
            clock += m; // the moment this phone is ready
            total += clock;
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(leastTotalWait(new int[] {7, 2, 4}));
        System.out.println(leastTotalWait(new int[] {5}));
        System.out.println(leastTotalWait(new int[] {3, 3, 3}));
        System.out.println(leastTotalWait(new int[] {12, 3, 7, 3, 20, 1, 9, 5}));
        int[] largest = new int[200_000]; // the largest input the limits allow
        Arrays.fill(largest, 10_000);
        System.out.println(leastTotalWait(largest));
    }
}

// The repair queue: the smallest total waiting time is reached by repairing the shortest jobs first.
#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>

std::int64_t least_total_wait(std::vector<int> minutes) {  // a copy: the caller's vector stays as it was
    std::ranges::sort(minutes);
    std::int64_t clock = 0, total = 0;  // 64 bits: the total reaches 2.00001e14, far above a 32-bit int
    for (int m : minutes) {
        clock += m;  // the moment this phone is ready
        total += clock;
    }
    return total;
}

int main() {
    std::println("{}", least_total_wait({7, 2, 4}));
    std::println("{}", least_total_wait({5}));
    std::println("{}", least_total_wait({3, 3, 3}));
    std::println("{}", least_total_wait({12, 3, 7, 3, 20, 1, 9, 5}));
    std::println("{}", least_total_wait(std::vector<int>(200'000, 10'000)));  // the largest input the limits allow
}

// The repair queue: the smallest total waiting time is reached by repairing the shortest jobs first.
package main

import (
	"fmt"
	"slices"
)

func leastTotalWait(minutes []int) int64 {
	order := slices.Clone(minutes) // sort a copy, not the caller's slice
	slices.Sort(order)
	var clock, total int64 // int64 says how wide the total is, whatever the platform's int
	for _, m := range order {
		clock += int64(m) // the moment this phone is ready
		total += clock
	}
	return total
}

func main() {
	fmt.Println(leastTotalWait([]int{7, 2, 4}))
	fmt.Println(leastTotalWait([]int{5}))
	fmt.Println(leastTotalWait([]int{3, 3, 3}))
	fmt.Println(leastTotalWait([]int{12, 3, 7, 3, 20, 1, 9, 5}))
	largest := make([]int, 200_000) // the largest input the limits allow
	for i := range largest {
		largest[i] = 10_000
	}
	fmt.Println(leastTotalWait(largest))
}

The Java, C++ and Go versions are built and run with the commands you would type in a terminal:

from session import run, versions

# Waiting.java runs as a single source file, waiting.cpp is built with the sanitizers on, and go run builds waiting.go.
versions("java -version", "clang++ --version", "go version")
run("""
java Waiting.java
clang++ -std=c++23 -O2 -Wall -Wextra -fsanitize=address,undefined waiting.cpp -o waiting && ./waiting
go run waiting.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Waiting.java
21
5
18
171
200001000000000
$ clang++ -std=c++23 -O2 -Wall -Wextra -fsanitize=address,undefined waiting.cpp -o waiting && ./waiting
21
5
18
171
200001000000000
$ go run waiting.go
21
5
18
171
200001000000000

"""Runs shell commands one at a time and prints the session as a terminal would show it.

Each command is printed after "$ ", then everything it wrote (standard output and standard error together, in order).
A command that fails adds "[exit status N]", and the script then exits with status 1, so that no record is kept of a
session whose programs did not build. Java 25 (Temurin) and Go 1.27.1, the versions this track pins, come from the
mise installations folder beside the Python that runs this file; clang++ is the system compiler.
"""
import os
import re
import subprocess
import sys
from pathlib import Path

INSTALLS = Path(sys.executable).resolve().parents[3]  # .../installs/python/3.14.8/bin/python3 -> .../installs
TOOLCHAINS = [INSTALLS / "java" / "temurin-25.0.4+101.0.LTS" / "bin", INSTALLS / "go" / "1.27.1" / "bin"]
RELEASE_DATE = re.compile(r"\s+\d{4}-\d{2}-\d{2}")  # a version line may carry a release date; pages show no dates


def environment():
    env = dict(os.environ)
    env["PATH"] = os.pathsep.join([*map(str, TOOLCHAINS), env.get("PATH", "")])
    env["GOTOOLCHAIN"] = "local"  # build with the Go that is installed, never download another
    env["GOTELEMETRY"] = "off"
    return env


def shell(command):
    return subprocess.run(command, shell=True, env=environment(), stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)


def versions(*commands):
    """Prints the first line of each version command as a comment."""
    for command in commands:
        result = shell(command)
        lines = result.stdout.splitlines()
        if result.returncode != 0 or not lines:
            sys.exit(f"{command} did not run: a pinned toolchain is missing")
        print(f"# {RELEASE_DATE.sub('', lines[0])}")


def run(script):
    """Runs each line of script as one command and prints it with its output."""
    failed = False
    for command in filter(None, (line.strip() for line in script.splitlines())):
        print(f"$ {command}", flush=True)
        result = shell(command)
        print(result.stdout, end="", flush=True)
        if result.returncode != 0:
            print(f"[exit status {result.returncode}]")
            failed = True
    if failed:
        sys.exit(1)

Each language needs one decision about the total, which reaches 200,001,000,000,000:

• Python integers have no fixed size, so the total is always exact. sorted() returns a new list and leaves the caller’s list as it was.
• JavaScript numbers hold whole numbers exactly up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1 (about 9 × 10¹⁵), well above this total. Without a comparison, sort() compares the values as text, so 10000 would sort before 2; pass (a, b) => a - b.
• Java keeps the clock and the total in long, a 64-bit integer. Arrays.sort on an int[] is a dual-pivot quicksort whose documentation promises O(n log n) on all inputs, and java Waiting.java runs a single source file without a separate compile step (JEP 330).
• C++ uses std::int64_t and std::ranges::sort, which makes O(n log n) comparisons. std::println needs -std=c++23, and the sanitizer flags turn an overflow into a report at run time.
• Go says int64, because the language specification lets int be 32 or 64 bits wide. slices.Clone and slices.Sort leave the caller’s slice as it was.

Checking it against the brute force

A proof can hide a slip, so check the code too. This stress test compares shortest first with the brute force on 3,000 random queues, with two rules that look just as reasonable beside it:

"""Shortest repair first against the brute force on 3,000 random queues, and two rules that look just as reasonable."""
import random
from itertools import permutations


def total_wait(minutes):
    clock = total = 0
    for m in minutes:
        clock += m
        total += clock
    return total


def brute_force(minutes):
    return min(total_wait(order) for order in permutations(minutes))


RULES = {
    "shortest first": lambda q: total_wait(sorted(q)),
    "longest first": lambda q: total_wait(sorted(q, reverse=True)),
    "the order given": total_wait,
}

rng = random.Random(8)
wrong = dict.fromkeys(RULES, 0)
first_wrong = {}
for _ in range(3000):
    queue = [rng.randint(1, 9) for _ in range(rng.randint(1, 6))]  # short repairs, so equal times come up often
    best = brute_force(queue)
    for name, rule in RULES.items():
        if rule(queue) != best:
            wrong[name] += 1
            first_wrong.setdefault(name, (queue, rule(queue), best))
for name in RULES:
    line = f"{name:<16} wrong on {wrong[name]:>5,} of 3,000 queues"
    if name in first_wrong:
        queue, got, best = first_wrong[name]
        line += f", first on {queue}: {got} instead of {best}"
    print(line)

shortest first   wrong on     0 of 3,000 queues
longest first    wrong on 2,411 of 3,000 queues, first on [6, 7]: 20 instead of 19
the order given  wrong on 2,051 of 3,000 queues, first on [4, 1]: 9 instead of 6

Shortest first matched the brute force on all 3,000 queues. The two rules beside it show what a stress test is for: longest first was wrong on 2,411 queues, the first of them [6, 7], and keeping the order given was wrong on 2,051. Repair times from 1 to 9 make equal lengths common, so ties were tested thousands of times too.

Edge cases and common bugs

• One phone, or equal repairs: one phone’s total is its own repair time, and equal repairs need no tie-break, because any order among them gives the same total.
• Adding the repair to the total instead of the clock: the result is the sum of all repairs, the same for every order. It passes the one-phone example, which is why tests need queues of three phones or more.
• Sorting the wrong way: sorted(minutes, reverse=True) out of habit is the longest-first rule of the stress test.
• A 32-bit total: Java’s int wraps round without a word, and in C++ signed overflow is undefined behaviour. The fifth example catches both.
• Sorting the caller’s list in place: list.sort(), or Arrays.sort on the input, changes data the caller may still need. Sort a copy unless the problem allows it.
• Another meaning of waiting: if a wait ends when the repair starts, every wait is shorter by that customer’s own repair, so the total falls by the sum of all repairs, the same in every order, and the best order does not change.

When greedy is the wrong tool

Some signs say early that a greedy rule is unlikely to hold:

• The brute force finds a counterexample. That settles it, however good the rule sounds.
• The choices share a budget and interact: the capacity of a bag, an exact amount to pay, a deadline that several jobs compete for. One choice that looks good can waste the room that two better ones needed.
• The proof needs a step the problem forbids, such as splitting an item or moving a job past one that must come first.
• The question counts ways or asks for every answer. A greedy algorithm builds one answer and has nothing to count.

Then look for dynamic programming, which keeps every option open until it can compare them, or for a different key that the stress test cannot break. Every rule in this lesson, with its verdict:

Practise: the first amount where greedy goes wrong

Turn the coin check into a function of your own. The sample tests include coin systems without a 1, where greedy can be left with a remainder it cannot pay, amounts that no coins add up to, a limit that is itself the answer, and a limit of 20,000.

first_greedy_failure([1, 3, 4], 10)              # 6: greedy pays 4 + 1 + 1, the fewest is 3 + 3
first_greedy_failure([1, 2, 5, 10, 20, 50], 70)  # -1: greedy is right for every amount up to 70
first_greedy_failure([3, 5], 20)                 # 6: greedy takes 5 and is left with 1, but 3 + 3 works

def first_greedy_failure(coins, limit):
    """The smallest amount from 1 to limit that largest-coin-first pays badly, or -1 if there is none."""
    # Replace this line with your code.
    return -1

from coins import first_greedy_failure


def test_examples():
    """the two systems of the prompt"""
    assert first_greedy_failure([1, 3, 4], 10) == 6
    assert first_greedy_failure([1, 2, 5, 10, 20, 50], 70) == -1


def test_coins_in_any_order():
    """the coins may come in any order"""
    assert first_greedy_failure([4, 1, 3], 10) == 6
    assert first_greedy_failure([25, 1, 10], 100) == 30


def test_coins_list_unchanged():
    """the caller's list of coins is left as it was"""
    coins = [4, 1, 3]
    first_greedy_failure(coins, 10)
    assert coins == [4, 1, 3]


def test_limit_is_included():
    """an amount equal to limit is checked, and nothing above it"""
    assert first_greedy_failure([1, 3, 4], 6) == 6
    assert first_greedy_failure([1, 3, 4], 5) == -1
    assert first_greedy_failure([1, 29, 30], 58) == 58
    assert first_greedy_failure([1, 29, 30], 57) == -1


def test_greedy_gets_stuck():
    """without a 1 coin, greedy can be left with a remainder that another choice avoids"""
    assert first_greedy_failure([3, 5], 20) == 6
    assert first_greedy_failure([5, 7], 30) == 10
    assert first_greedy_failure([9, 6, 4], 30) == 8


def test_amounts_nobody_can_pay():
    """an amount that no coins add up to is not a failure of greedy"""
    assert first_greedy_failure([2], 9) == -1
    assert first_greedy_failure([7], 100) == -1
    assert first_greedy_failure([3, 5], 5) == -1


def test_systems_where_greedy_works():
    """systems where largest-first is always right, checked up to their two largest coins added together"""
    for coins in ([1, 2, 3], [1, 5, 10, 25], [1, 2, 4, 8, 16], [1, 3, 9, 27], [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000]):
        largest, second = sorted(coins)[-2:][::-1]
        assert first_greedy_failure(coins, largest + second) == -1, coins
    assert first_greedy_failure([1], 50) == -1


def test_first_failures():
    """the first failure of twelve more systems"""
    expected = {
        (1, 4, 5): 8, (1, 6, 10): 12, (1, 7, 10): 14, (1, 10, 25): 30, (1, 5, 8): 10, (1, 11, 20): 22,
        (1, 2, 6, 7): 12, (1, 5, 12, 25): 15, (1, 9, 16, 20): 18, (1, 15, 20, 50): 30, (2, 7): 8, (3, 7, 11): 9,
    }
    for coins, amount in expected.items():
        assert first_greedy_failure(list(coins), 100) == amount, coins


def test_large_limit():
    """ten coins and a limit of 20,000, within the time limit"""
    assert first_greedy_failure([1, 2, 5, 10, 20, 50, 100, 200, 500, 1000], 20_000) == -1
    assert first_greedy_failure([1, 2, 5, 10, 20, 50, 100, 200, 500, 600], 20_000) == 1000

Interview questions

What is the difference between an exchange argument and a stays-ahead argument?

Both prove that a greedy rule is optimal, from opposite ends. An exchange argument starts from a best answer and edits it: wherever the best answer differs from greedy’s, swap greedy’s choice in and show that the answer stays valid and gets no worse, so after enough swaps the best answer has become greedy’s. Shortest job first is proved this way, because swapping a longer job that runs just before a shorter one lowers the total wait. A stays-ahead argument compares instead: choose a measure for partial answers, such as where the k-th booking ends, and show by induction that after every step greedy’s measure is at least as good as any other answer’s. Use an exchange when the answer is an order or a set you can edit, and stays ahead when the answer grows step by step.

Largest coin first fails for coins of 1, 3 and 4. How would you find a failure like that quickly in a round?

Do not guess amounts by hand. Compute the fewest coins for every amount from 0 up with a small dynamic program: the fewest for an amount is one more than the fewest for the amount minus some coin, the best over all coins that fit. Then run largest first on each amount and stop at the first that uses more coins. For 1, 3 and 4 that is 6: greedy pays 4 + 1 + 1, the best is 3 + 3. It takes about a dozen lines and runs in milliseconds. To know how far to check, use the bound of Kozen and Zaks: if a system with a 1 coin fails at all, its first failure is at most its two largest coins added together, 7 here. Checking every amount up to that sum settles the whole system.

Key takeaways

• A greedy rule is a claim. It is safe only when its first choice belongs to some best answer and what is left is the same problem, smaller.
• Break a rule before you prove it: a brute force on small inputs finds counterexamples quickly, and the smallest one shows which choice went wrong.
• An exchange argument edits any best answer into greedy’s one swap at a time without making it worse; a stays-ahead argument shows that greedy is never behind after any number of steps.
• Largest coin first is right for 1, 2, 5, 10, 20, 50 and wrong for most systems you could invent, such as 89 % of the four-coin systems with coins up to 30. For a system with a 1 coin, check every amount up to the two largest coins added together.
• Value per kilogram is optimal when items can be cut and wrong for whole items, because the swap its proof needs is not allowed.
• Shortest job first minimises the total wait: a longer job just before a shorter one is always worth swapping. Keep the total in 64 bits.