Clinic #29: Non-overlapping Intervals

A catalogue of ways to attack a problem. Its greedy panel says the rule out loud: take the locally best choice, never look back, and prove the choice safe. This clinic is that proof, done once by hand on a real problem.

Before you start. Clinic #28: Merge Intervals took a pile of road closures, sorted them by where they start, and walked the road once, widening one sign at a time; if you have not read it, the one thing to carry over is that an interval is a start and an end, like “km 2 to km 6”. Sorting costs a little more than one pass, written O(n log n), and trying every subset of n things costs O(2ⁿ), which doubles with each item you add; Sorting & Searching shows where the first one comes from.

The idea in 30 seconds

LeetCode 435 asks for the fewest intervals to remove so none overlap, which is n minus the most you can keep.
Here, intervals that only touch ([1,2], [2,3]) do not overlap, the opposite of Merge Intervals (LeetCode 56), so the keep test is start >= last_end, the end of the last one kept.
Keeping the earliest start fails ([9,17] blocks three), and keeping the shortest fails ([16,19] sits across the gap).
Sort by end and keep whatever fits: the booking that leaves first always leaves the most room.
The proof is an exchange argument: swap the first booking of any best schedule for the earliest-ending one and nothing clashes, so greedy loses nothing.
Merge Intervals sorts by start and widens one stretch; this sorts by end and cancels.

Read the story · Skip to the numbers