Line Sweep · bigonotes

Comparing every pair of intervals is $O(n^2)$ . A line sweep imagines a vertical line moving left to right along the axis and stops only where something changes: where an interval opens or closes. Sort those events once and a single pass answers "how many overlap at once?", "where is everyone free?" or "does the load ever exceed capacity?" in $O(n \log n)$ .

The idea#

Most positions on the axis are boring: between two consecutive events, nothing changes. So you never scan the axis itself; you jump from event to event. Every sweep has three ingredients.

Events. Each interval becomes two events, an open and a close. Each event carries a payload: +1 and -1 for counting, +w and -w for weights, or an insert and a delete for an object.
A sorted order. Sort events by coordinate. The line only ever moves forward, so each interval is added once and removed once.
An active state. A running count or sum, or a structure holding what's currently under the line. Opens add, closes remove, and at the right moments you record an answer.

The third ingredient is the one that changes most between problems, because the active state decides what you can answer:

Active state	Answers
Counter or running sum	How many are active, total load
Heap	Which active item ends soonest, largest active item
Sorted structure (BST)	Nearest neighbor among the active items
Hash set	Is this item active?
Fenwick or segment tree	Range aggregates over the active items

The tie-break decides "touching"#

Step 2 above sorts by coordinate, but that leaves one gap. When an open and a close share a coordinate, the order you process them in changes the answer. Decide what you want to be true at the exact shared point.

Touching is a conflict (inclusive intervals, [1, 5] and [5, 8] share time 5): process opens first, so both are alive at that point.
Touching is fine (one meeting ends as the next begins): process closes first, so the old one leaves before the new one arrives.

This is the most bug-prone part of any sweep. Two coincident events in the wrong order give a silent off-by-one.

How to spot it#

A sweep fits when the problem lives on a line and asks about what overlaps. Look for these cues:

Objects live on an ordered axis: time, an x-coordinate, a value.
The question is about overlap, coverage, depth, capacity or gaps along that axis.
You care how many are active, not who.
Brute force compares all pairs.

Template#

This is the counting sweep, with a counter as the active state. Only the payload, the tie-break and the moment you record change between problems.

events = empty list
for each (start, end) in intervals:
    add (start, +1) to events        # open
    add (end, -1) to events          # close
sort events by coordinate, then by the tie-break
active = best = 0
for each (x, delta) in events:
    active += delta                  # update first
    best = max(best, active)         # then record
return best

For [[1, 5], [5, 10]] this returns 2 when touching conflicts (opens first) and 1 when it doesn't (closes first). In Python, a plain tuple sort puts -1 before +1, so it processes closes first. Sorting on (x, -delta) processes opens first.

Difference array or line sweep?#

A Difference Array is a special case of a sweep: it gives every index its own slot and accumulates at the end. Pick by the shape of the input.

Use a difference array when	Use a line sweep when
Indices are small (about $2 \times 10^5$ or less)	Coordinates are huge (up to $10^9$ )
Updates are static	Events must be handled in order
You only need the final accumulated array	You need the state at each event (max overlap, gaps)
The axis is a plain 1D index range	You need an active set: heap, BST, geometry

Pitfalls#

These are the mistakes that most often cost a correct answer.

Wrong tie-break. Ask "at the shared point, should both be alive?" before you write the sort key.
Reading the answer at the wrong time. Update the count first, then record the maximum.
Treating it as the main intervals tool. Sweeps are for depth, capacity and gaps. Merging, scheduling and covering are sort-key problems; see Intervals: Choose the Sort Key.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the two Meeting Rooms problems.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Meeting Rooms

Process closes first: once someone leaves a room, another meeting can start. Read the count as 1 for in a meeting, 0 for free and 2 for a clash. If it ever reaches 2, return false.

Hint: Meeting Rooms II

The number of rooms is the maximum overlap. A meeting that ends at 5 frees its room for one that starts at 5, so process closes first.

Hint: Divide Intervals Into Minimum Number of Groups

The number of groups is the maximum overlap again. The intervals are inclusive, so [1, 5] and [5, 8] clash at 5. Process opens first.

Hint: Car Pooling

The payload is +passengers at pickup and -passengers at drop-off. Fail as soon as the running total exceeds the capacity. The plain tuple sort puts drop-offs first on ties, which matches "the seat is free at the drop-off point".

Hint: Employee Free Time

Sweep every employee's busy intervals together. When the count drops to 0, everyone is free, so a gap starts at that coordinate. When the count next rises to 1, the gap ends. Opens first stops touching intervals from producing a zero-length gap.

Hint: My Calendar III

Bookings arrive one at a time, and each call asks for the current maximum overlap. Keep the events in a sorted map from coordinate to delta, and re-sweep it after each booking.

Hint: The Skyline Problem

A counter is not enough: you need the tallest building under the line. Use a heap (or sorted structure) of active heights as the active state, and record a key point whenever the maximum height changes.

Key takeaways#

Most positions are boring: jump between events instead of scanning the axis.
Every sweep is events + a sorted order + an active state.
The tie-break at a shared coordinate decides whether touching counts: opens first means it conflicts, closes first means it doesn't.
The active structure (counter, heap, BST) decides which questions you can answer.
A difference array is the small-index, final-state-only special case of a sweep.

Core idea#

Turn each interval into an open and a close event. Sort the events and sweep once with a running state, in $O(n \log n)$ instead of comparing every pair.

Key points#

Every sweep has events, a sorted order and an active state.
Between two events nothing changes, so jump from event to event.
Payloads: +1 / -1 to count, +w / -w for weights.
Update the count first, then record the maximum.
The active state sets what you can answer: a counter for load, a heap for the soonest end, a sorted structure for the nearest neighbor.
Spot it: an ordered axis, a question about overlap, depth, capacity or gaps, and "how many" not "who".
Gaps (Employee Free Time): a gap starts when the count drops to 0 and ends when it rises to 1.

The tie-break decides touching#

At a shared point	Process first	Sort key	Example
Touching is a conflict	opens	`(x, -delta)`	Minimum Number of Groups
Touching is fine	closes	plain tuple sort	Meeting Rooms II, Car Pooling

Template#

events = empty list
for each (start, end) in intervals:
    add (start, +1) and (end, -1) to events
sort events by coordinate, then by the tie-break
active = best = 0
for each (x, delta) in events:
    active += delta                  # update first
    best = max(best, active)         # then record
return best

Pitfalls#

Wrong tie-break. Ask "at the shared point, should both be alive?" first.
Recording before updating the count.
Using a sweep for merging, scheduling or covering. Those are sort-key problems.
Small indices and only a final state needed? A difference array is simpler.

Say it in an interview#

"Each interval becomes two events, and one pass over sorted events gives the max overlap."
"Opens first means touching conflicts. Closes first means it does not."