Earliest finish first

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four slots: [1,2], [2,3], [3,4], [1,3]. Remove as few as possible so that none of the remaining ones overlap. (Touching at a point, like [1,2] and [2,3], is not an overlap.) Here removing just [1,3] works: [1,2], [2,3], [3,4] fit together. So the answer is 1.

By hand you might try every subset to keep: 16 subsets for 4 slots, 2ⁿ in general, which is a million for 20 slots and impossible for 100. You need a rule for choosing.

What makes a slot a good one to keep? It should leave as much room as possible for the others. The slot that ends earliest leaves the most room, because everything that starts after its end can still be kept. [1,2] ends at 2; [1,3] ends at 3. Keeping [1,2] blocks only things that start before 2; keeping [1,3] blocks things that start before 3. So prefer the early finisher.

Build the structure, one piece at a time

Piece 1: sort by end time. [1,2], [2,3], [1,3], [3,4]. (Two slots end at 3; either order works.)

Piece 2: one number, the last kept end. Start it at "nothing kept", say −∞.

Piece 3: the rule. Walk the sorted slots. If a slot starts at or after the last kept end, keep it and update the last kept end to its end. Otherwise it overlaps something kept: remove it.

Three kept, one removed. The removed count is the answer; equivalently, the kept count is the largest set of non-overlapping slots.

Why it is correct

The invariant: after processing the first i slots in end order, the kept set is a largest possible non-overlapping set among those i slots, and among all such largest sets it has the earliest last end.

The argument is an exchange. Suppose some best solution S does not keep the earliest-ending slot a. Look at the first slot b that S keeps. Since a ends no later than b, replacing b with a in S cannot create an overlap with the later slots of S (they all start after b ends, hence after a ends). The new set is just as large and now agrees with the greedy choice. Repeating this for every greedy choice turns S into the greedy set without ever losing a slot, so the greedy set is as large as any best solution.

end(a) ≤ end(b) and start(c) ≥ end(b) ⇒ start(c) ≥ end(a)

Sorting by start instead would fail: [1,100] would be kept first and block everything. The end time is what measures how much room a slot leaves.

Why it is fast

Sorting is O(n log n). The walk looks at each slot once with one comparison.

time = O(n log n), versus 2ⁿ subsets

For 100 slots that is about 700 steps instead of a number with 30 digits.

How to recognise it in an interview

The cues are "maximum number of non-overlapping intervals", "minimum removals so none overlap", "schedule the most activities", "minimum arrows to burst balloons" (each arrow covers a point, and sorting by end lets one arrow at the earliest end pop every balloon that contains it). Say: "Sort by end time and greedily keep every interval that starts after the last kept end; an exchange argument shows the earliest finisher is always safe."

Non-overlapping Intervals is the example above. Minimum Number of Arrows to Burst Balloons keeps a slot exactly when a new arrow is needed, so the kept count is the arrow count. Maximum Number of Events That Can Be Attended adds a day-by-day sweep with a heap of end days, the same preference for early finishers.

02The idea in one line

Sort by end; take an interval whenever it starts after the last chosen end.

Reach for it when: Non-overlapping intervals, arrows to burst balloons, activity selection.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Non-overlapping Intervals on [[1,2],[2,3],[3,4],[1,3]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort by end: the interval that finishes first leaves the most room
2. [1,2]: nothing kept yet, keep it, end = 2
3. [2,3] starts at 2 ≥ last end 3: keep it, end = 3
4. [1,3] starts at 1 < last end 3: it overlaps, remove it
5. [3,4] starts at 3 ≥ last end 4: keep it, end = 4
6. Kept 3, removed 1: the minimum removals
7. Earliest finish first is optimal by exchange: O(n log n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Intervals: Sort and merge intervals, Sweep line (events ±1).