Sweep Line Template

Problem Statement

Given an array of intervals, return the maximum number of intervals that overlap at any single point — the canonical application of the sweep-line technique, and the template that generalises to Meeting Rooms II, Calendar III, Car Pooling, and the Skyline Problem.

Input

An array of intervals [[start, end], …] on the number line.

intervals = [[1,4],[2,5],[7,9]]

Output

A single integer — the maximum overlap count reached at any point along the timeline.

2

Constraints

• 1 ≤ intervals.length ≤ 10⁵
• intervals[i].length == 2
• -10⁹ ≤ startᵢ ≤ endᵢ ≤ 10⁹

Intuition

Instead of processing intervals as whole units, decompose each into two events: a +1 at its start and a -1 at its end. Sort all events by time (ties broken by delta — ends before starts for closed semantics). Sweep left-to-right maintaining a running counter; the peak value is the answer.

Events:   (1,+1)  (2,+1)  (4,-1)  (5,-1)  (7,+1)  (9,-1)
 
Sweep timeline:
Time:      1    2    3    4    5    6    7    8    9
Delta:    +1   +1         -1   -1        +1        -1
Active:    1    2    2    1    0    0    1    1    0
                ↑ peak = 2  ← answer

Solution

def sweepLine(intervals: list[list[int]]) -> int:
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
 
    # Sort: by time; on ties, ends (-1) before starts (+1)
    events.sort(key=lambda x: (x[0], x[1]))
 
    active = max_active = 0
    for _, delta in events:
        active += delta
        max_active = max(max_active, active)
 
    return max_active

function sweepLine(intervals: number[][]): number {
    const events: [number, number][] = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);
        events.push([end, -1]);
    }
 
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
 
    let active = 0, maxActive = 0;
    for (const [, delta] of events) {
        active += delta;
        maxActive = Math.max(maxActive, active);
    }
 
    return maxActive;
}

Complexity

Edge Case Thinking