Card 05/ 08
Choosing the Key a Greedy Algorithm Sorts By
The same jobs sorted by length or by deadline give different worst lateness, and only one key is provably right.
Most greedy algorithms sort the items and then take them in order, so the real design decision is the key they sort by: the same items sorted two ways give two different answers, and usually only one of them is best. This card shows the key deciding the answer on one set of jobs, gives the right key for three common goals, and says how to test a key.
Suppose a workshop has four jobs to run one at a time, each with a duration and a deadline in days, and wants the latest job to be as little late as possible. A job's lateness is how far past its deadline it finishes, or 0 if it finishes on time. The jobs are A (3 days, due day 3), B (1 day, due 6), C (2 days, due 8) and D (4 days, due 9). Doing the short jobs first sounds sensible, since it gets the most work done early. A run tried that and the alternative, earliest deadline first.
| Order | First | Second | Third | Fourth | Worst lateness |
|---|---|---|---|---|---|
| Shortest first | B days 0 to 1, on time | C days 1 to 3, on time | A days 3 to 6, 3 late | D days 6 to 10, 1 late | 3 |
| Earliest deadline first | A days 0 to 3, on time | B days 3 to 4, on time | C days 4 to 6, on time | D days 6 to 10, 1 late | 1 |
Shortest first pushes A, the job due soonest, back to day 6. Earliest deadline first finishes everything by day 10, as any order must, and only D is late. The run also tried all 24 orders, and none did better than 1.
The key is the decision because everything after the sort is the same loop. The table below gives the right key for three goals that look alike, and for each a wrong key with the small input that breaks it, all from the run.
| Goal | Sort by | A wrong key and its counterexample |
|---|---|---|
| Most meetings in one room | End time, earliest first | Start time: 0 to 9, 1 to 3, 3 to 5 keeps only 0 to 9, where 2 fit |
| Least total waiting, adding up when each job finishes | Duration, shortest first | Longest first: jobs of 10 and 1 days wait 10 + 11 = 21, against 1 + 11 = 12 |
| Smallest worst lateness | Deadline, earliest first | Duration: the four jobs above, worst lateness 3 against 1 |
A sort key is a guess until it survives two tests. First, try to break it: build inputs of two or three items where the key's first choice looks costly, as each row's counterexample does. Second, try to prove it with an exchange argument: take two neighbouring items out of the key's order and show that swapping them never makes the answer worse. Earliest deadline first passes. Swap two neighbouring jobs so that the one due sooner runs first: it now finishes earlier, and the other finishes when the pair used to finish. Its deadline is the later of the two, so it is no more late than the job due sooner was before the swap.
When no key passes both tests, the problem is not greedy. The van on Practice: Loading a Van by Value per Kilo is one where a key works for one version of the problem and no key works for the other.
← → move through sections and cards