The idea: one room, as many meetings as possible

You have one room and a list of meetings, each with a start and a finish time. Two meetings that overlap can't both use the room. Which meetings should you keep so that the room hosts as many of them as possible? This is interval scheduling, also called activity selection. A meeting is written [s, f): it runs from s up to f, so one meeting can end at 4 and the next start at 4.

Nine meetings A to I drawn as bars on a time line from 0 to 18. The five kept by earliest finish time, B [1,4), D [5,8), F [8,11), G [11,14) and H [14,17), are green and sit one after another; the other four are grey.
The page's 9 meetings: earliest finish time keeps B, D, F, G, H, five meetings, and no choice of meetings does better.

Earliest finish time

A greedy algorithm makes one choice at a time and never takes it back. The greedy that works here is: always keep the meeting that ends first.

  1. Sort the meetings by finish time.
  2. Remember free = the time the room becomes free, at first 0.
  3. Go through the meetings in that order. If a meeting starts at or after free, keep it and set free to its finish time. Otherwise skip it.

On the page, the blue line is free. B ends first (at 4), so it is kept. C starts at 2, before 4, so it is skipped. D starts at 5 and is kept, E starts at 7 before D ends at 8, and so on: B, D, F, G, H. (Demo: earliest finish time) The sort takes O(n log n) time and the pass O(n). Ending early is what matters: the meeting that ends first leaves the most time for everything after it.

Two greedies that look right but fail

Other rules sound just as natural, and a small example breaks each one.

  • Earliest start first. A meeting that starts early can run very long. A [0, 12) starts first, so it is kept, and it blocks B to G. Only H fits after it: 2 meetings instead of 5. (Demo: earliest start fails)
  • Shortest first. A short meeting can sit across two others. E [7, 9) is the shortest, so it is kept first, and it blocks both D [5, 8) and F [8, 11): 4 meetings instead of 5. (Demo: shortest first fails)
Left: earliest start keeps the long meeting A from 0 to 12, which overlaps B, C, D, E, F and G; only H fits after it, 2 meetings, marked wrong. Right: shortest first keeps E from 7 to 9, which overlaps both D from 5 to 8 and F from 8 to 11, so the chain loses one, 4 meetings, marked wrong.
Earliest start is broken by one long early meeting; shortest first by one short meeting that overlaps two.

A third idea, "keep the meeting with the fewest overlaps", also fails, on a slightly bigger example. Testing a greedy on a few cases is not enough: it needs a proof.

Why earliest finish is optimal: the exchange argument

Let G = g1, g2, … be greedy's meetings and O = o1, o2, … any optimal schedule, both in time order. We change O into G without ever making it worse.

  1. g1 is the meeting that ends first of all, so g1 ends no later than o1. Replace o1 by g1: o2 starts after o1 ends, so also after g1 ends. O still has no overlap and the same size.
  2. Now O and G agree on the first meeting. After it, greedy again took the meeting that ends first, so the same swap works for o2, then o3, and so on.
  3. At the end O = G for the first |O| meetings. O can't have one more: it would start after O's last meeting ends, which is after G's last ends, and greedy would have kept it too. So |G| = |O|.

The demo uses O = C, D, F, G, I, another optimal schedule (it is what you get by running greedy from the right: latest start first). B replaces C (4 ≤ 5), D, F and G are the same, and H replaces I (17 ≤ 18). (Demo: exchange argument)

Before: greedy G is B, D, F, G, H and the optimal O is C, D, F, G, I. B ends at 4, no later than C at 5, so C is swapped for B; H ends at 17, no later than I at 18, so I is swapped for H. After: O is B, D, F, G, H, still 5 meetings, the same as G.
Each swap puts greedy's meeting in O; it ends no later, so nothing after it breaks, and O keeps its size.

The demos in numbers

strategysort keykept on the 9 meetingscount
earliest finish timefinishB, D, F, G, H✓ 5
earliest start timestartA, H✗ 2
shortest firstlengthB, E, G, H✗ 4

The score line checks each answer against all 2n subsets of meetings. Press Random Set for new meetings: earliest finish time always reaches the best count, the other two only sometimes. (Demo: random set)

Related problems

If each meeting has a weight (a price) and you want the largest total, no greedy works; sort by finish time and use dynamic programming instead, much like the 0/1 knapsack. If every meeting must happen and you want the fewest rooms (interval partitioning), sort by start time and reuse a room as soon as it is free. See also Greedy vs DP Coin Change, where the largest coin first is a greedy that fails, and Huffman Coding, another greedy proved optimal by an exchange argument.

What the page leaves out

Times are whole numbers from 0 to 18 and a set has at most 10 meetings, so the brute-force check stays small. The page leaves out weighted interval scheduling, interval partitioning with several rooms, the "greedy stays ahead" style of proof, the fewest-overlaps counterexample, and online versions where meetings arrive one at a time.