Sweep Line

You have a list of meetings and need to find the minimum number of conference rooms required. Meetings overlap in complicated ways: some nest inside others, some partially overlap, some are completely disjoint. Trying to reason about pairs of intervals quickly becomes overwhelming. The sweep line technique cuts through this complexity by converting the problem from "which intervals overlap?" into "how many intervals are active at each moment in time?"

The core idea

The sweep line decomposes each interval into two point events: a +1 event at the start (an interval begins) and a -1 event at the end (an interval finishes). You then sort all events by time and sweep left to right, maintaining a running count. At any moment, the running count tells you how many intervals are simultaneously active. This transforms a two-dimensional problem (intervals have both start and end) into a one-dimensional scan over sorted events.

Meeting Rooms II: the motivating problem

LeetCode 253. Meeting Rooms II asks: given an array of meeting time intervals [[start, end], ...], find the minimum number of conference rooms required.

Why sweep line works here

Each meeting occupies a room from its start time until its end time. The number of rooms needed at any instant equals the number of meetings happening at that instant. The answer is the maximum of this value across all time.

Walked example

Consider the meetings [[0, 30], [5, 10], [15, 20]].

Step 1: Create events.

Step 2: Sort events by time. They are already sorted. When a start and end happen at the same time, process the end first. A room freed at time 10 can be reused by a meeting starting at time 10.

Step 3: Sweep through, tracking the running count.

• Time 0: count = 0 + 1 = 1
• Time 5: count = 1 + 1 = 2
• Time 10: count = 2 - 1 = 1
• Time 15: count = 1 + 1 = 2
• Time 20: count = 2 - 1 = 1
• Time 30: count = 1 - 1 = 0

The maximum count reached is 2, so we need 2 conference rooms. This matches intuition: meetings [0,30] and [5,10] overlap from time 5 to 10.

Let us try a denser example: [[1, 5], [2, 6], [3, 7], [4, 8]].

Events sorted: (1,+1), (2,+1), (3,+1), (4,+1), (5,-1), (6,-1), (7,-1), (8,-1).

Sweep:

• Time 1: count = 1
• Time 2: count = 2
• Time 3: count = 3
• Time 4: count = 4 (peak)
• Time 5: count = 3
• Time 6: count = 2
• Time 7: count = 1
• Time 8: count = 0

All four meetings are active simultaneously between times 4 and 5, so 4 rooms are needed.

Code

def minMeetingRooms(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends
    # Sort by time; if tied, process ends (-1) before starts (+1)
    events.sort(key=lambda x: (x[0], x[1]))

    max_rooms = 0
    current = 0
    for time, delta in events:
        current += delta
        max_rooms = max(max_rooms, current)
    return max_rooms

The sort is $O(n \log n)$ and the sweep is $O(n)$, giving $O(n \log n)$ overall. Space is $O(n)$ for the events list.

Tie-breaking matters

Why process ends before starts at the same time? If meeting A ends at time 10 and meeting B starts at time 10, they do not actually overlap, because the room is freed and immediately reused. Processing the -1 before the +1 at time 10 ensures the count does not spike to 2 when only 1 room is needed. If the problem defines intervals as closed on both ends (i.e., [1, 10] and [10, 20] do conflict), reverse the tie-breaking rule.

The Skyline Problem

LeetCode 218. The Skyline Problem is a harder application of the sweep line. You are given a list of buildings, each described as [left, right, height], and must output the skyline contour, the list of key points where the maximum height changes.

Why this is harder than Meeting Rooms

In Meeting Rooms, the "value" at each event is simply +1 or -1. In the Skyline Problem, each building has a different height, and you need the maximum height among all active buildings at every point, not just the count. This requires a data structure to track active building heights efficiently.

The approach

1. Create events. For each building [left, right, height], create a start event at left (building appears with its height) and an end event at right (building disappears).

1. Sort events by x-coordinate. Tie-breaking: if two events share the same x, process starts before ends (a building that starts and another that ends at the same x, where the new building may maintain the height). Among starts at the same x, process taller buildings first. Among ends at the same x, process shorter buildings first.

1. Sweep with a max-heap (or sorted multiset) tracking the heights of all currently active buildings. At each event:
2. - If it is a start event, add the height to the heap.
3. - If it is an end event, remove the height from the heap.
4. - After processing, check the current maximum height. If it differs from the previous maximum, record a key point.

Walked example

Buildings: [[2, 9, 10], [3, 7, 15], [5, 12, 12]].

Events (sorted):

• x=2: start height 10
• x=3: start height 15
• x=5: start height 12
• x=7: end height 15
• x=9: end height 10
• x=12: end height 12

Sweep:

Output: [[2, 10], [3, 15], [7, 12], [12, 0]].

Building [3,7,15] rises above building [2,9,10] at x=3, creating a height jump. When it ends at x=7, building [5,12,12] takes over as the tallest active building. When the last building ends at x=12, the skyline drops to 0.

Code

import heapq

def getSkyline(buildings):
    events = []
    for left, right, height in buildings:
        events.append((left, -height, right))   # start: negative height for sorting
        events.append((right, 0, 0))             # end: height 0 signals end event
    events.sort()

    # Max-heap of (height, end_x). Use negative heights for Python min-heap.
    # Seed with ground level that never expires.
    heap = [(0, float('inf'))]
    result = []
    prev_max = 0

    for x, neg_h, end in events:
        if neg_h != 0:
            # Start event: add building to heap
            heapq.heappush(heap, (neg_h, end))
        # Lazy deletion: remove buildings that have ended
        while heap[0][1] <= x:
            heapq.heappop(heap)
        current_max = -heap[0][0]
        if current_max != prev_max:
            result.append([x, current_max])
            prev_max = current_max

    return result

This uses lazy deletion: instead of removing a building from the heap the moment it ends, we leave it in place and discard it when it reaches the top and we discover it has expired. The amortized cost is still $O(n \log n)$ since each building is pushed and popped at most once.

Encoding trick: Start events store (-height, end_x) so the Python min-heap acts as a max-heap by height. End events use (right, 0, 0). When we sort, start events at the same x come before end events (because -height < 0), and taller starts come first (more negative), which is exactly the tie-breaking we need.

Other applications

The sweep line pattern appears in many interval and coordinate problems.

LeetCode 1094. Car Pooling: Passengers board at a pickup location and exit at a drop-off location. Each trip has a number of passengers. Create +passengers events at pickups and -passengers events at drop-offs. Sweep through and check whether the running total ever exceeds the vehicle capacity.

LeetCode 732. My Calendar III: Each call books a new event. Return the maximum number of concurrent events (the maximum k-booking) after each booking. This is essentially a dynamic version of Meeting Rooms II: maintain a sorted map of events, and after each insertion, sweep to find the peak.

LeetCode 56. Merge Intervals: While typically solved with a sort-and-merge approach, you can also use a sweep line. Create +1/-1 events, and wherever the count drops to 0 marks the end of a merged interval.

Sweep line vs. interval merging

Both techniques deal with collections of intervals, but they solve different questions.

Interval merging groups overlapping intervals into larger ones. It sorts by start time, then makes a single pass, extending the current interval whenever the next one overlaps. The output is a simplified set of non-overlapping intervals. It answers "what are the combined ranges?"

Sweep line processes events in time order and tracks a value (count, max height, total passengers) as intervals begin and end. It answers "what is the state at each point in time?", and in particular, "what is the peak state?" The events carry weights or attributes, and you accumulate them with a running aggregate.

The key difference: interval merging cares about the intervals themselves, while sweep line cares about what happens between the intervals: the aggregate state over time. When you need a global maximum, minimum, or threshold check across overlapping intervals, reach for the sweep line.

Complexity summary

The sweep line is one of the most versatile techniques for interval and geometry problems. Once you learn to see intervals as pairs of events and time as a dimension to sweep across, a wide family of problems becomes approachable with the same framework: decompose, sort, sweep, aggregate.

Recognizing this pattern

You're probably looking at a sweep line when:

• You have intervals or events on a timeline and need to count overlaps or find max concurrency.
• Words like "meeting rooms," "skyline," "car pooling," or "calendar bookings" appear in the prompt.
• A range update over many intervals followed by point queries, the difference-array twin of sweeping.
• You'd otherwise compare every pair of intervals; sorting events collapses it to one pass.

Common templates:

• Max concurrency: emit +1 at each start, −1 at each end, sort, sweep, track running sum. Example: Meeting Rooms II.
• Range increment with difference array: apply +k at start and −k just after end, prefix-sum at the end. Example: Car Pooling.
• Skyline / heights: sweep x-coordinates; a max-heap tracks active building heights. Example: The Skyline Problem.
• Booking with capacity check: sweep through bookings, reject when the running sum would exceed capacity. Example: My Calendar III.