Many interval and geometry problems look two-dimensional and messy — until you sweep. The line sweep technique slides an imaginary vertical line across the input from left to right and only stops at events: the sorted x-coordinates where something changes. Turn every interval into two events — +1 where it starts, −1 where it ends — sort them, and walk through with a running counter. The counter’s peak is the maximum overlap: the fewest meeting rooms you need. Step the line and watch the count rise and fall.
O(n log n) — the sort dominates · one linear pass over sorted events · +1 start, −1 end
event
A sorted x-coordinate where the state changes — here, an interval start or end.
+1 / −1
A start adds one to the active count; an end removes one.
active count
How many intervals overlap the sweep line right now.
peak
The maximum active count over the whole sweep — the maximum overlap.
sweep.js — sort events, walk the line
Ready
Six intervals (think meetings). Each becomes two events: +1 at its start, −1 at its end. We sort all events by position and sweep left to right, tracking how many overlap. Step to the next event.
–
sweep at
0
active now
0
max overlap
How it works
The whole trick is trading a hard continuous question — “over the entire timeline, what is the most that ever overlap?” — for a finite, discrete one. The overlap count only ever changes at an interval’s endpoints, so those endpoints are the only places worth looking. Sort them, and a single pass with a +1/−1 counter answers the question exactly. Handling ties correctly matters: process an end before a start at the same coordinate, so an interval ending exactly where another begins isn’t counted as overlapping.
1
Make events from endpoints
Turn each interval [s, e] into two events: a +1 at s and a −1 at e. The interior of the interval never needs to be examined — only where it changes.
2
Sort the events
Sort all events by x-coordinate. At ties, put −1 (end) before +1 (start) so touching intervals don’t falsely count as overlapping. This O(n log n) sort is the dominant cost.
3
Sweep with a running counter
Walk the sorted events left to right, adding each delta to a counter. The counter is the number of intervals overlapping the line at that moment.
✓
Track the peak
Keep the maximum value the counter ever reaches. That peak is the maximum overlap — for meetings, the minimum number of rooms you need. One linear pass after sorting.
Time
O(n log n)
Sweep pass
O(n)
Answers
max overlap
Generalizes
geometry
The code
# maximum overlap (min meeting rooms) via a line sweepdef max_overlap(intervals):
events = []
for s, e in intervals:
events.append((s, +1)) # interval starts
events.append((e, -1)) # interval ends
events.sort(key=lambda ev: (ev[0], ev[1])) # end (-1) before start (+1) at ties
active = best = 0
for x, delta in events:
active += delta
best = max(best, active) # the peak is the answerreturn best
Quick check
1. Why does the line sweep only stop at interval endpoints?
Between endpoints, the set of active intervals is constant, so the count doesn’t change. Only starts (+1) and ends (−1) move it — so those finite points are the only places worth examining.
2. At a tie (an interval ends exactly where another starts), which event goes first?
Processing the end (−1) before the start (+1) at the same coordinate means an interval that ends exactly where another begins isn’t double-counted as overlapping — which matches the meeting-rooms interpretation.
3. What dominates the running time of a line sweep?
Creating events is O(n) and the sweep pass is O(n). Sorting the events is O(n log n) and dominates, which is the standard cost of sweep-line algorithms.
FAQ
What is a line sweep algorithm?
A technique that solves geometric and interval problems by moving an imaginary line across the input and processing a sorted sequence of events where the state changes. For interval overlap, each interval adds a +1 at its start and −1 at its end; sweeping the sorted events with a counter gives the max overlap in O(n log n).
What problems does the line sweep solve?
Maximum interval overlap and meeting rooms, merging intervals, segment-intersection detection (Bentley–Ottmann), union area of rectangles, closest pair of points, and many map-overlay and range problems. The common thread: the answer only changes at a finite set of sortable events.
How does line sweep relate to interval scheduling?
Both process sorted interval endpoints but answer different questions. Interval scheduling greedily picks the most non-overlapping intervals (sorting on end times); a line sweep counts overlaps or detects interactions as the line passes. Both sort endpoints and make one pass.
Can a line sweep run in more than one dimension?
Yes. In 2D the sweep line moves along one axis while a secondary balanced-BST "status structure" tracks what it currently intersects, ordered along the other axis — as in Bentley–Ottmann segment intersection and rectangle-union area, achieving O((n + k) log n).
SOLVE IT YOURSELF
Solve it: how many meetings overlap at once
Stop thinking about intervals and start thinking about events. Sort the moments something starts or ends, walk the timeline, and the answer falls out of a single counter. Python or TypeScript.
YOUR TASK
Implement max_overlap(intervals): given [start, end] pairs, return the largest number of intervals active at any one moment. An interval ending exactly when another starts does not overlap it.
HINTS — 6 IDEAS
Turn each interval into two events: (start, +1) and (end, −1). The intervals themselves stop mattering.
Sort the events by time, then sweep, keeping a running counter and its maximum.
The subtle part is ties. At the same timestamp, ends must be processed before starts, or back-to-back meetings look like an overlap.
Sorting (t, −1) before (t, +1) happens for free if you sort the pairs directly, since −1 < +1 — a small trick worth recognising rather than special-casing.
This is O(n log n) from the sort alone; the sweep itself is a single linear pass with one integer of state.
The same sweep shape solves merging intervals, skyline problems and rectangle unions — only the event payload changes.