Greedy algorithms

A greedy algorithm builds an answer step by step, each time taking the choice that looks best right now and never taking it back. It is usually a sort and one pass, so its time complexity is O(n \log n), but it gives the right answer only for some problems. When a choice can turn out wrong later, use dynamic programming instead.

Explanation

A cashier gives 18 in change with coins of 1, 2, 5 and 10. The natural way is to take the largest coin that still fits: 10, then 5, then 2, then 1. That is 4 coins, the fewest possible.

Fig. 1. The largest coin that fits, each time: 4 coins for 18.

This is a greedy algorithm. The same rule can fail. With coins of 1, 3 and 4, pay 6. The largest coin first gives 4 + 1 + 1, three coins, but 3 + 3 is only two.

Fig. 2. Paying 6 with coins 1, 3 and 4.

For coins like 1, 3 and 4, coin change tries every possible last coin instead.

Here is a problem where the right rule is less obvious. A meeting room gets 7 talks for one day, each with a start and an end hour. Take as many talks as possible so that no two overlap. A talk may start at the moment the previous one ends.

Fig. 3. Seven talks on one day. Each bar runs from the talk's start to its end.

Trying every set of talks means 128 sets for 7 talks and 2^n for $n$ talks (brute force), too many for large $n$. A greedy way is to take one talk, skip every talk that overlaps it, and repeat. Which talk do we take first?

The first try is starts first: the talk that starts earliest, talk 1, from 9 to 17. After it the rule takes talk 6, from 17 to 20, and talk 7 then overlaps it: 2 talks. Yet talks 2, 4, 5 and 7 fit together: the best schedule has 4 talks.

Fig. 4. Starts first: 2 talks (red).

Short talks leave more room, so the next try is shortest first. Talks 3 and 7 both last 2 hours; take talk 3, from 12 to 14. But it overlaps talks 2 and 4, and both are in the best schedule. After talk 3 the rule takes talks 7 and 5: 3 talks.

Fig. 5. Shortest first: 3 talks (red).

Once a talk is taken, the talks after it depend only on when it ends. The talk that ends first frees the room as early as possible, so it leaves the most time for the rest. In practice, sort the talks by end time and go through them once. This rule, ends first, is the greedy rule for this problem.

The cells show the talks sorted by end time: 2, 3, 4, 1, 5, 6, 7. Ends first goes through them in this order.

Talk 2, from 10 to 13, ends first. The room is free, so it is taken, and the dashed line moves to 13: the room is free from 13. The outlined talk is the one looked at.

Talk 3 starts at 12, before 13, so it is skipped.

Talk 4 starts at 13, exactly when the room is free, so it is taken. The room is free from 16.

Talk 1 starts at 9, before 16, so it is skipped.

Talk 5 starts at 16, exactly when the room is free, so it is taken. The room is free from 19.

Talk 6 starts at 17, before 19, so it is skipped.

Talk 7 starts at 19, exactly when the room is free, so it is taken. The room is free from 21. Ends first takes talks 2, 4, 5 and 7: 4 talks.

1/8

Fig. 6. Step through ends first with the buttons or the arrow keys. Green talks are taken, grey talks are skipped, and the dashed line marks the moment the room is free. The cells below show the order after sorting.

The run takes talks 2, 4, 5 and 7. After the sort, each talk is looked at once, so the work is the sort, O(n \log n) (time complexity).

In C++

Each use below has the same shape: sort by the rule, then take or skip each item in one pass.

Most talks

Each talk is a pair, sorted with a plain sort. In the pass, s and e are a talk's start and end, and freeFrom is the moment the room is free.

The input is $n$, then $n$ lines "start end". For the 7 talks it is:

7
9 17
10 13
12 14
13 16
16 19
17 20
19 21

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> talks(n);   // {end, start}
    for (auto& [e, s] : talks) cin >> s >> e;

    // sort by the rule: ends first
    sort(talks.begin(), talks.end());

    // take or skip
    int count = 0;
    int freeFrom = 0;   // the room is free from this moment; times are not negative
    for (auto [e, s] : talks) {
        if (s >= freeFrom) {
            count++;
            freeFrom = e;
        }
    }
    cout << count << '\n';
}

Fewest coins

For coins 1, 2, 5 and 10, go through the coins from the largest and take as many of each as fit:

int count = 0;
for (int c : {10, 5, 2, 1}) {
    count += x / c;   // as many coins c as fit into x
    x %= c;           // what is left to pay
}

Other coin sets need their own check: compare largest first with brute force on small amounts, or use coin change.

Pans and lids

Each pan needs a lid at least as large as itself; cover as many pans as possible. Sort both, and give each pan, smallest first, the smallest free lid that fits. The index j points to the smallest unused lid.

sort(pans.begin(), pans.end());
sort(lids.begin(), lids.end());
int covered = 0, j = 0;
for (int p : pans) {
    while (j < (int)lids.size() && lids[j] < p) j++;   // skip lids too small for this pan
    if (j == (int)lids.size()) break;                  // no lids left
    covered++;
    j++;                                               // this lid is used
}

Fig. 7. Each pan, smallest first, takes the smallest free lid that fits. Lid 2 fits no pan.

A lid too small for this pan is too small for every larger pan, so skipping it loses nothing. Giving a pan the smallest lid that fits keeps the larger lids for the larger pans. Pans and lids takes O(n \log n) for the two sorts. Both programs use $O(n)$ memory.

Correctness proof

To prove the rule, we show that ends first never loses: some best schedule starts with the talk that ends first.

Take any best schedule. Its first talk ends no earlier than the greedy's first talk, which ends earliest of all. Replace it with the greedy's talk. The other talks of the schedule start after the replaced talk ended, so they also start after the greedy's talk ends. Nothing overlaps, and the count is the same. The swap needs only that the schedule has no overlaps, so it also works on talks 3, 5 and 7, which is not best: talk 3 ends at 14 and talk 2 at 13, so talks 2, 5 and 7 still fit.

Fig. 8. Talk 2 (green) ends first, so it can replace talk 3. The rest still fits.

Now skip every talk that starts before the greedy's talk ends, and the same argument applies to the talks that are left. Here talk 4, from 13 to 16, now fits between talks 2 and 5. So the greedy takes as many talks as a best schedule.

This proof is called an exchange argument, the usual way to prove a greedy rule: show that any best answer can be changed, one exchange at a time, into the greedy's answer without getting worse. For coins 1, 3 and 4 it fails: the best payment of 6, 3 + 3, has no 4, and no exchange puts a 4 into it without adding coins.

Common mistakes

• Trusting a rule because it passes the sample. Shortest first takes all 4 films that fit on the festival above, but only 3 of the 4 talks. Compare a rule with brute force on small random inputs, or prove it with an exchange argument.

• Taking the largest coin first for any coins. It can fail to pay at all: for coins 2 and 5 it pays 8 as 5 + 2 and is left with 1, though 2 + 2 + 2 + 2 works. Use coin change.

• Using >= when a talk must start strictly after the previous one ends. On the films, >= takes A, C, E and F, but then at most 2 fit, such as A and E. Use s > freeFrom there.

• Taking the best value per kilogram first in a knapsack. With room for 10 kg and unlimited items of 5 kg worth 10 and 6 kg worth 19, the best ratio gets 19 with one 6 kg item, but two 5 kg items give 20. Use knapsack DP.

Similar techniques

Brute force tries every answer: use it when $n$ is small.

Knapsack with items that can be cut (the fractional knapsack) is solved by the best value per kilogram first.

Sweep line keeps a running state over intervals in time order, such as how many overlap.

Two pointers moves through two sorted arrays, as in pans and lids.

Kruskal's, Prim's and Dijkstra's algorithms are greedy algorithms on graphs, each with its own proof.

Practice