Greedy Algorithms

A cashier owes you 63 cents in coins of 25, 10, 5 and 1. Nobody teaches cashiers an algorithm, yet they all do the same thing: hand over the biggest coin that still fits, and repeat. 25, 25, 10, 1, 1, 1. Six coins, and you cannot do it with fewer.

That habit has a name. A greedy algorithm builds its answer one step at a time, and at each step takes whatever looks best right now. It never reconsiders. Compare that with backtracking, which tries every option and undoes the bad ones. Greedy tries one option per step, so it is fast. The catch is that "best right now" is not always best overall.

#The idea: commit to one choice

Take a concrete problem. One meeting room, six booking requests, each with a start and end hour. You want to accept as many bookings as possible, and no two accepted bookings may overlap. A booking that ends at 6 and one that starts at 6 are fine together.

There are several greedy rules you could try. Take the shortest booking first. Take the one that starts earliest. Take the one that ends earliest. Only the last one is always right, and the reason is simple: the booking that ends first leaves the room free for the longest possible time afterwards. Nothing you could pick instead leaves more room for the rest.

So the algorithm is: sort the bookings by end time. Walk through them. Keep a booking if it starts at or after the end of the last one you kept; otherwise skip it.

#Bookings, traced

sort bookings by end timefor each (start, end) in order:  if start < lastEnd: skip  else: keep it; lastEnd = end

// bookings: [start, end] pairs. Back-to-back bookings are allowed.
function maxBookings(bookings) {
  const byEnd = [...bookings].sort((a, b) => a[1] - b[1]);
  let kept = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of byEnd) {
    if (start >= lastEnd) { // fits after the last booking we kept
      kept++;
      lastEnd = end;
    }
  }
  return kept;
}
 
maxBookings([[2, 5], [6, 8], [1, 3], [1, 7], [4, 6], [7, 9]]); // 3

# bookings: [start, end] pairs. Back-to-back bookings are allowed.
def max_bookings(bookings):
    by_end = sorted(bookings, key=lambda b: b[1])
    kept = 0
    last_end = float("-inf")
    for start, end in by_end:
        if start >= last_end:  # fits after the last booking we kept
            kept += 1
            last_end = end
    return kept
 
max_bookings([[2, 5], [6, 8], [1, 3], [1, 7], [4, 6], [7, 9]])  # 3

#Why earliest end is safe

"It looks right" is not a proof. Two of the three rules above also look right, and they are wrong. The standard way to prove a greedy choice is an exchange argument.

Let X be the booking that ends first. Take any best schedule, one with the most bookings. Look at its first booking, Y. Y cannot end before X, because X ends first of all. Now swap Y out and X in. X ends no later than Y did, so it cannot clash with anything that came after Y. The schedule is still valid and has the same number of bookings.

So there is always a best schedule that starts with X. Taking X is never a mistake. After that, the rest is the same problem on the bookings that start at or after the end of X, and the same argument applies again.

Try the same swap with the other rules and it breaks. Earliest start picks 1–10 out of 1–10, 2–3 and 4–5, and blocks both short meetings: 1 booking instead of 2. Shortest first picks 4–7 out of 1–5, 4–7 and 6–10, and it overlaps both others: 1 instead of 2.

#When greedy fails

Back to the cashier. In a country with coins worth 1, 3 and 4, make 6. The biggest coin that fits is 4. That leaves 2, which needs 1 + 1. Greedy hands over three coins. But 3 + 3 is two coins.

The exchange argument fails here. Take the best answer, 3 + 3, and swap one 3 for the greedy coin 4. You get 4 + 3 = 7, which is too much. Any answer that starts with 4 has to make the remaining 2 out of 1s. The first coin changes what is left to solve, and greedy never looks ahead to see that.

With coins 25, 10, 5 and 1 the swap always works, which is why the cashier is safe. The code is the same; only the coin set decides whether it is correct.

// coins sorted from largest to smallest
function greedyChange(coins, amount) {
  let used = 0;
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      used++;
    }
  }
  return amount === 0 ? used : -1; // -1: greedy got stuck
}
 
greedyChange([25, 10, 5, 1], 63); // 6, the true minimum
greedyChange([4, 3, 1], 6);       // 3, but 3 + 3 needs only 2

# coins sorted from largest to smallest
def greedy_change(coins, amount):
    used = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            used += 1
    return used if amount == 0 else -1  # -1: greedy got stuck
 
greedy_change([25, 10, 5, 1], 63)  # 6, the true minimum
greedy_change([4, 3, 1], 6)        # 3, but 3 + 3 needs only 2

The right tool for coins in general is dynamic programming, which works out the best answer for every smaller amount instead of betting on one coin.

#How to tell

Before trusting a greedy idea, run it through three checks.

1. Hunt for a counterexample. Try tiny inputs, 2 or 3 items, built to trap the rule: a long item that starts first, a big coin that leaves an awkward remainder. Most wrong greedy rules die in a minute here.
2. Try the exchange argument. Take any best answer and swap in the greedy choice. If it is always still valid and no worse, the rule is safe.
3. Watch for choices that change the future. If taking an item uses up a budget or reshapes what is left, like a coin changing the remaining amount or an item filling a weight limit, greedy is suspect. That smells like knapsack, a dynamic programming problem.

#Common mistakes

#Check yourself

#What to practise next

Intervals builds on the bookings problem: merging overlapping ranges and counting how many rooms you need. For problems where greedy fails, like the odd coin sets, go to Dynamic Programming.