Sweep Line
01 / The one-sentence essence
Turn intervals into +1 / −1 events at their endpoints, sort by position, then sweep — at every event the running active count moves by one. The answer is always some property of that step function.
Problemmax concurrent intervalsInput[0,30] [5,10] [15,20]
Input has 3 intervals. Each will contribute one +1 event at its start and one −1 event at its end.
step
0 / 9
active
0
best
—
0 / 9
02 / The pattern signature
# intervals → endpoint eventsevents ← []for [s, e] in intervals:events.push((s, +1))events.push((e, −1))events.sort() # tie-break depends on the questionactive ← 0; best ← 0for (x, d) in events:active += dbest ← max(best, active)# `best` is the max concurrent — the canonical answer
03 / When to recognize this pattern
"max concurrent / at the same time"
The textbook trigger. Meetings overlapping, planes airborne, cars on a highway, employees on shift — anything where you want the peak of the active count. Each interval contributes one +1 and one −1; the rest is bookkeeping.
"booking / reservation / pickup-dropoff"
A capacity check disguised as a list of bookings. The events sort tells you whether the load ever exceeds the limit. Bonus: easy to early-exit at the first violation.
"intervals — what is true at every point"
When the answer doesn't change between events. The step function only changes at the endpoints, so checking each event covers every distinct moment in time.
"skyline / coverage / union length"
A sweep line + a side data structure (heap, balanced BST, multiset). Each event inserts or removes a value; the answer at that x is read off the structure's top.
04 / Common pitfalls
i.
Tie-breaking events at the same x.
When a
+1 and a −1 share an x, ordering matters. For concurrent meetings (endpoints touch counts as overlap), apply +1 first. For passengers in a car (dropoff happens before pickup at the same stop), apply −1 first. Same skeleton, opposite tie-break.ii.
Confusing this with merge intervals.
Merge intervals collapses overlapping ranges into one output range and counts groups. Sweep line tracks the running depth over time. They both sort by start, but only sweep line cares about the −1 events — without them you can't see when the depth drops.
iii.
Forgetting the running count is between events too.
The active count is constant on the segment
(prev_x, x] — between events nothing changes. If the question asks "for how long is the count exactly k", sum the gaps where active == k, not just the event counts themselves.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.