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]
intervals[0,30][5,10][15,20]events
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

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.
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.
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

easy4

01Meeting Rooms— LC 252→02Rectangle Overlap— LC 836→03Maximum Population Year— LC 1854→04Check if All the Integers in a Range Are Covered— LC 1893→

medium9

01Meeting Rooms II— LC 253→02Range Addition— LC 370→03Non-overlapping Intervals— LC 435→04Minimum Number of Arrows to Burst Balloons— LC 452→05My Calendar II— LC 731→06Car Pooling— LC 1094→07Corporate Flight Bookings— LC 1109→08Shifting Letters II— LC 2381→09Divide Intervals Into Minimum Number of Groups— LC 2406→

hard15

01The Skyline Problem— LC 218→02Contains Duplicate III— LC 220→03Count of Smaller Numbers After Self— LC 315→04Count of Range Sum— LC 327→05Perfect Rectangle— LC 391→06Reverse Pairs— LC 493→07My Calendar III— LC 732→08Employee Free Time— LC 759→09Rectangle Area II— LC 850→10Maximum Profit in Job Scheduling— LC 1235→11Minimum Number of Taps to Open to Water a Garden— LC 1326→12Minimum Interval to Include Each Query— LC 1851→13Minimum Cost to Reach Destination in Time— LC 1928→14Meeting Rooms III— LC 2402→15Minimum Time to Complete All Tasks— LC 2589→