Sweep line

Problem

Merging intervals tells you what is covered, but it forgets how deeply. Many questions care about depth: the most meetings happening at once (so the number of rooms), whether a car ever carries more passengers than it has seats, or which of the active intervals is the shortest at a given point. Checking every point in time against every interval is O(n · T). The sweep replaces time with the 2n moments where something changes.

Intuition

Imagine a vertical line sliding across a timeline from left to right. Between events nothing changes, so the line only needs to stop where an interval starts or ends. At each stop it updates a small summary of what it is crossing: a count, a load, or a heap of the intervals currently under it. The answer is read off that summary, either at its peak or at the query points.

The only subtle part is ties. If one meeting ends at 5 and another starts at 5, does the line see both at once? For half-open meetings it should not, so the end is processed first. Sorting events as (time, change) with −1 for ends does this automatically, because −1 sorts before +1.

At time 5 one meeting ends and another starts. Ending first keeps the count at 3 instead of a false 4. The diagram scrolls sideways on a narrow screen.

Mechanics

Counting with events

Make the list of events (start, +1) and (end, −1) for every interval and sort it. Walk it, adding each change to a running count. Invariant: after processing every event at times ≤ t, the count equals the number of intervals with start ≤ t < end, which is exactly the intervals active just after t. Each interval contributes +1 once its start has passed and cancels it once its end has passed, so the count is right. The rooms needed are the peak of the count: at the peak moment that many meetings overlap and need separate rooms, and at no moment are more needed.

Two sorted arrays instead of one event list

An equivalent trick sorts the start times and the end times as two separate lists and walks them with two pointers. When the next start is earlier than the next end, a meeting begins (count up); otherwise one finishes (count down). Using < rather than ≤ processes ends first on ties. This works because the count only depends on how many starts and how many ends have passed, not on which meeting they belong to.

A heap of end times

When you need to know which intervals are active, keep them in a min-heap keyed by end time. Process intervals in start order; before adding one, pop every end time ≤ its start, since those meetings are over and their rooms are free. The heap's size is the number of rooms in use, and its largest size is the answer. This is the same sweep, but the heap remembers each active interval.

Difference arrays

When coordinates are small integers, skip the sort: write +k at each start and −k at each end into an array indexed by position, then take prefix sums. The running sum at position x is the total load over x. Every interval costs O(1), and one pass rebuilds the whole profile.

Each trip writes two numbers; the bars come from one left-to-right running sum. Passengers leave at their drop-off, so a drop-off and a pickup at the same place never overlap.

Sweeping queries

"For each point q, what is the smallest interval containing q?" Sort the queries and the intervals by start. For each query in increasing order, push every interval with start ≤ q onto a heap keyed by length, then pop from the top while the top's end is < q. Popping is safe because queries only increase, so an interval that ended before this query can never contain a later one. Intervals that ended but are not on top stay in the heap (lazy deletion) and are discarded only when they surface. Answers are written back to each query's original index.

Worked example

Rooms by events. For meetings [1, 5), [2, 6), [4, 8), [5, 9), [8, 10), [11, 12):

The peak is 3, so 3 rooms are needed.

Rooms by heap. The same meetings in start order, with the end times still occupying rooms:

The heap never holds more than 3 end times, matching the event count.

Car pooling. Trips (passengers, pickup, drop-off) (2, 1, 4), (3, 2, 6), (2, 5, 8), (1, 7, 9) write the changes 0, 2, 3, 0, -2, 2, -3, 1, -2, -1, whose running sums are 0, 2, 5, 5, 3, 5, 2, 3, 1, 0. With 5 seats the trips fit; with 4 seats the load first goes over at location 2.

Employee free time. All busy intervals in start order are [1, 3], [2, 4], [2, 5], [6, 7], [9, 12]. They merge to [1, 5], [6, 7], [9, 12], so everyone is free during [5, 6] and [7, 9].

Smallest interval per query. Intervals [2, 5], [1, 8], [4, 6], [7, 7], [10, 14] (length = end − start + 1), queries 9, 3, 12, 5, 7 visited in sorted order:

In the original query order the answers are -1, 4, 5, 3, 1. At query 7, [2, 5] has already ended but stays in the heap because [7, 7] is on top; it is popped later, at query 9.

Implementation

def min_rooms(meetings):
    events = []
    for start, end in meetings:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()                 # (t, -1) before (t, 1): a room is freed before it is reused
    rooms = best = 0
    for _, change in events:
        rooms += change
        best = max(best, rooms)
    return best

Variations and edge cases

import heapq


def min_rooms_heap(meetings):
    ends = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)


def car_pooling(trips, capacity):
    change = [0] * (max(end for _, _, end in trips) + 1)
    for passengers, start, end in trips:
        change[start] += passengers
        change[end] -= passengers
    load = 0
    for delta in change:
        load += delta
        if load > capacity:
            return False
    return True


def smallest_containing(intervals, queries):
    intervals = sorted(intervals)
    heap, i, answers = [], 0, {}
    for q in sorted(set(queries)):
        while i < len(intervals) and intervals[i][0] <= q:
            start, end = intervals[i]
            heapq.heappush(heap, (end - start + 1, end))
            i += 1
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        answers[q] = heap[0][0] if heap else -1
    return [answers[q] for q in queries]

• Tie order. Sorting (time, +1) before (time, −1) over-counts back-to-back meetings. Closed intervals, where touching ones do overlap, need the opposite order.
• The heap answer is its size at the end. In min_rooms_heap the heap only grows when no room is free, so its final size is the peak. If you pop several ended meetings per step, track the maximum size instead.
• Big coordinates. A difference array over times up to 10⁹ is too large; sort the events or compress the coordinates first.
• Repeated queries. Answer each distinct query once and map back, or keep the original indices as the helper on this page does.
• Drop-off at the end index. In car pooling the passengers leave at end, so the change goes at end, not end + 1; for closed ranges it would be end + 1.

Complexity and tradeoffs

• Brute-force baseline: compare every pair of intervals, O(n²), or mark every integer point that each interval covers, O(n · L) for lengths up to L. One sort replaces both.
• Event sweep: O(n log n) to sort 2n events, O(n) space.
• Heap of end times: O(n log n) time, O(n) space in the worst case; it costs a little more than counting but knows which intervals are active.
• Difference array: O(n + C) time and O(C) space for coordinates up to C; no sort at all, which beats the sweep when C is small.
• Query sweep: O((n + q) log n) after sorting both, against O(n · q) for checking every interval for every query.
• When it is the wrong tool. If intervals and queries arrive online and interleaved, there is no global order to sweep; use a balanced tree, a segment tree or a Fenwick tree over compressed coordinates. If you only need coverage, plain merging is simpler.

Problems

Meeting Rooms II is the canonical sweep: solve it with events, with two sorted arrays and with a heap. Car Pooling is the difference-array form. The two Hard problems combine the sweep with merging (free time) and with a heap that answers sorted queries.

Medium

• 253. Meeting Rooms II Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Sort the start times and end times separately and sweep them, so the rooms in use rise at each start and fall at each end.
• 1094. Car Pooling NeetCode 250
  Add passengers at each pickup and subtract them at each drop-off, then sweep the locations to check the capacity is never exceeded.

Hard

• 759. Employee Free Time Grind 169
  Merge all employees' busy intervals in start order, and the gaps between merged blocks are the common free time.
• 1851. Minimum Interval to Include Each Query NeetCode 150 NeetCode 250
  Process queries in sorted order, adding intervals that have started to a heap by size and discarding ones that already ended.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 252. Meeting Rooms Easy
• 1834. Single-Threaded CPU Medium
• 632. Smallest Range Covering Elements from K Lists Hard
• 2402. Meeting Rooms III Hard

Connections

The difference array is prefix sums run backwards: write changes, then integrate. Employee Free Time can also be solved as a k-way merge of each employee's already-sorted schedule. Processing items in sorted order while a heap holds the candidates is the same shape as the two-heaps IPO problem, and the event sweep is the one-dimensional case of the sweep-line algorithms of computational geometry.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, section 33.2 on sweeping in computational geometry, and exercise 16.1-4 on scheduling activities into the fewest lecture halls (the rooms problem).
• Shamos, M. I. and Hoey, D., "Geometric intersection problems", 17th Symposium on Foundations of Computer Science, 1976, which introduced the sweep-line technique.
• Skiena, S., The Algorithm Design Manual, section 4.1 on applications of sorting and the catalog's computational geometry chapter.
• Sedgewick and Wayne, Algorithms, section 2.4 on priority queues.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.