The Sweep Line Technique for Interval and Geometry Questions

Many interval problems look different but share one solution shape: turn every interval into events, sort the events, and sweep across them while keeping a small amount of state. That's the sweep line technique.

The template

def max_overlap(intervals):
    events = []
    for s, e in intervals:
        events.append((s, +1))
        events.append((e, -1))
    events.sort(key=lambda x: (x[0], x[1]))   # ends before starts at the same time
    cur = best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

This answers "minimum meeting rooms" in O(n log n): the answer is the peak number of simultaneously open intervals.

Tie-breaking is the real question

If one meeting ends at 10:00 and another starts at 10:00, do they overlap? For half-open intervals [s, e) they don't, so process the end (−1) before the start (+1) at equal times. For closed intervals, do the opposite. Saying this out loud shows care; getting it wrong is the most common bug.

Swap the state, keep the sweep

• Counter: meeting rooms, max concurrent users, car pooling capacity.
• Heap of active heights: the skyline problem: at each x, the outline height is the max active height, and you emit a point when it changes.
• Balanced set of active segments: detecting any segment intersection (Shamos-Hoey) in O(n log n).
• Running union length: total covered length or area of rectangles (with a segment tree over the compressed y-coordinates).

Difference arrays: the discrete cousin

When coordinates are small integers, skip sorting: add +1 at start and −1 at end in an array, then take a prefix sum. Range-increment problems ("apply k bookings, report each day's total") become O(n + range).

How to present it

"I'll convert each interval to a start and end event, sort by time with ends first at ties, and sweep while tracking the count of active intervals." Then mention the complexity and the tie rule. That framing usually earns full marks before you've written a line.

Disclosure: I work on Linkjob AI, an AI interview assistant. These are general practice notes.