Sweep line (events ±1)

38 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

Three meetings: [0,30], [5,10], [15,20]. How many rooms are needed so no two meetings share a room? At time 7 two meetings are running (the first and the second), at time 17 again two (the first and the third), and never three. So two rooms.

By hand you might check every moment: for each time from 0 to 30, count how many meetings cover it, and take the biggest count. That is 31 moments × 3 meetings. If times are in seconds over a year, it is thirty million moments, and the count only changes at a few of them.

The count only changes when a meeting starts (goes up by one) or ends (goes down by one). Between those moments nothing happens. So we only need to visit the start and end times, in order, and keep a running count.

Build the structure, one piece at a time

Piece 1: events. Turn each meeting into two events: (start, +1) and (end, −1). Our three meetings give six events: (0,+1), (30,−1), (5,+1), (10,−1), (15,+1), (20,−1).

Piece 2: sort the events by time. When a start and an end share the same time, put the end first: a meeting ending at 10 and another starting at 10 can share a room. Sorted: (0,+1), (5,+1), (10,−1), (15,+1), (20,−1), (30,−1).

Piece 3: sweep. Walk the events left to right, adding each ±1 to a running count, and remember the highest count seen.

The peak is 2, the number of rooms. The picture to hold in mind is a vertical line sweeping across a timeline of bars; the running count is how many bars the line is cutting through.

Why it is correct

The invariant: after processing all events with time ≤ t, the running count equals the number of meetings that are in progress at time t (started at or before t, not yet ended).

Each meeting contributes +1 once it starts and −1 once it ends, so at any time its net contribution is 1 while it is running and 0 otherwise. Summing over meetings gives exactly the number in progress. Since the count is constant between events, the maximum over all times equals the maximum over event times, which the sweep records.

Why is the peak the number of rooms needed? You need at least that many, because at the peak moment that many meetings run at once. And that many suffice: assign each starting meeting any free room; a room is free whenever the count is below the peak, which is always.

rooms = max over t of ∑_meetings [start ≤ t < end]

Why it is fast

There are 2n events. Sorting them costs O(n log n); the sweep is one pass of 2n additions.

time = O(n log n), independent of how long the timeline is

A year of seconds no longer matters; only the number of meetings does. The same result can be reached with two sorted arrays (all starts, all ends) and two pointers, or with a min-heap of end times; the event list is the version that generalises best, for example to adding +w passengers instead of +1.

How to recognise it in an interview

The cues are "minimum number of rooms", "maximum number overlapping at once", "busiest time", "how many are alive at time t", "capacity of a car along a route", "skyline". Any question about how many intervals cover a point, for every point. Say: "Each interval is a +1 at its start and a −1 at its end; sorting the events and keeping a running sum gives the coverage at every moment."

Meeting Rooms II is the example above. Car Pooling adds +passengers and −passengers and checks the running sum never exceeds the capacity. The Skyline Problem is a sweep where the running state is the set of active heights, kept in a heap, and the output is every moment the maximum height changes.

02The idea in one line

Turn intervals into +1/−1 events, sort, and sweep to track concurrency.

Reach for it when: Meeting rooms II, max concurrent, skyline, car pooling, busiest time.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Meeting Rooms II on [[0,30],[5,10],[15,20]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Turn each meeting into a +1 at start and a −1 at end
2. t = 0: start of [0,30], running = 1, a new peak
3. t = 5: start of [5,10], running = 2, a new peak
4. t = 10: end of [5,10], running = 1
5. t = 15: start of [15,20], running = 2, a new peak
6. t = 20: end of [15,20], running = 1
7. t = 30: end of [0,30], running = 0
8. The peak concurrency is the answer: 2 rooms
9. Sort 2n events, one sweep: O(n log n)

04Asked at Google

9 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, Earliest finish first.