Sweep Line and Event Counting

Merge Intervals works by comparing intervals to each other. That is the right tool when you need to combine them. But when the question is “how many overlap at the busiest moment?”, comparing pairs is the wrong frame — and $O(n^2)$.

The sweep line reframes it. Stop thinking about intervals as objects and think about the moments they change something:

An interval [start, end) is really two events: +1 at start and -1 at end.

Sort all the events by time, walk through them keeping a running total, and that total is the number of active intervals at every instant. The maximum it reaches is your answer.

What you’ll learn

• The +1 / -1 event transform, and why sorting events beats comparing intervals.
• The tie-breaking rule at a shared timestamp — which decides whether touching intervals count as overlapping.
• Inclusive vs. half-open endpoints, and the end + 1 fix.
• When a min-heap of end times is the better shape than events.
• Three real LeetCode problems solved in the browser: 1094, 2406, 253.

The cue

You are looking at a sweep line when…

• “Maximum number of overlapping” anything — meetings, cars, bookings — 253, 1094, 731, 732.
• “Minimum number of rooms / groups / machines” to fit everything. This is the same question: the answer equals the peak overlap.
• Resources are added and released over a timeline — 1094 Car Pooling.
• You need a running count across a range, not a merged range.
• Building a skyline or profile — 218 (a sweep line plus a heap).

The distinction from merge intervals: merging asks “what are the combined spans?” and outputs intervals. Sweeping asks “how many are active at once?” and outputs a count. Reach for merging when the output is intervals, sweeping when it is a number.

Why “minimum rooms” equals “peak overlap”

This equivalence is worth being able to state, because interviewers ask.

At the busiest instant, k meetings are genuinely simultaneous, so you cannot do with fewer than k rooms — that is the lower bound. And k rooms always suffice: sweep through time assigning each starting meeting any free room; at every instant at most k are active, so a free room always exists. Lower bound meets upper bound, so the minimum is exactly the peak.

Visual intuition

The sweep never asks “does A overlap B”. It only counts:

intervalSplit each interval into a +1 and a -1, then just add them upLC 253 · O(n log n)

rooms in use0peak0

1def min_meeting_rooms(intervals):2    events = []3    for s, e in intervals:4        events.append((s, +1))          # a meeting starts5        events.append((e, -1))          # a meeting ends6    events.sort()                       # ends sort BEFORE starts at equal time7    rooms = peak = 08    for _, delta in events:9        rooms += delta10        peak = max(peak, rooms)11    return peak

events8

setupForget the intervals as objects. Split each into two **events** — a +1 when it starts and a −1 when it ends — then sort all the events by time. The answer is the maximum the running total ever reaches, and no interval is ever compared with another.

Play‹›1/10⟲

Watch the tie-break at equal times: ends sort before starts, because a room vacated at t is available at t. Getting that backwards inflates the answer by one and is the single most common bug in this pattern.

The template

sweep_line_template.py

def max_overlap(intervals):
    """Peak number of simultaneously active [start, end) intervals."""
    events = []
    for start, end in intervals:
        events.append((start, 1))     # one more active from here
        events.append((end, -1))      # one fewer from here
 
    events.sort()                     # by time; -1 before +1 at equal times
 
    active = best = 0
    for _time, delta in events:
        active += delta
        best = max(best, active)
    return best
 
 
print(max_overlap([[0, 30], [5, 10], [15, 20]]))   # 2
print(max_overlap([[7, 10], [2, 4]]))              # 1

$O(n \log n)$ for the sort, then a single $O(n)$ pass. Space $O(n)$ for the events.

The tie-break at equal timestamps is the whole subtlety

When one interval ends exactly where another begins, do they overlap? For half-open [start, end) intervals — meetings, rides — no: the room is free the moment the meeting ends.

The template gets this right by accident of sorting, and it is worth understanding why. At the same time t, the tuples are (t, -1) and (t, 1). Python sorts tuples lexicographically and -1 < 1, so the departure is processed first — freeing capacity before the arrival consumes it. Exactly the desired behaviour, for free.

If instead endpoints are inclusive ([start, end], both occupied — as in LC 2406), touching intervals do conflict. Then you must push the release to end + 1:

python

events.append((start, 1))
events.append((end + 1, -1))     # inclusive end: still busy AT end

Getting this backwards is the single most common sweep-line bug, and it usually shows up only on the touching-intervals test case.

The heap alternative

For “minimum rooms” there is a second formulation that some find more intuitive: sort intervals by start, and keep a min-heap of end times of the currently-occupied rooms.

min_rooms_heap.py

import heapq
 
 
def min_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort()                       # by start time
    ends = []                              # min-heap of end times in use
    for start, end in intervals:
        if ends and ends[0] <= start:      # earliest-finishing room is free
            heapq.heappop(ends)            # reuse it
        heapq.heappush(ends, end)
    return len(ends)                       # rooms ever needed at once
 
 
print(min_rooms([[0, 30], [5, 10], [15, 20]]))   # 2

	Time	Space	Best when
Events	$O(n \log n)$	$O(n)$	You want the count, or the whole timeline profile
Min-heap of ends	$O(n \log n)$	$O(n)$	You need to know which room, or to track per-room state

Same complexity. The event version generalises better (it handles weights, as in LC 1094, and produces the full profile); the heap version tells you which resource is being reused, which matters if rooms have identities.

Dry run

intervals = [[0,30], [5,10], [15,20]] — LC 253’s example. Six events, sorted by time:

time	delta	active	best	what just happened
0	+1	1	1	[0,30] starts
5	+1	2	2	[5,10] starts while [0,30] is still running
10	−1	1	2	[5,10] ends
15	+1	2	2	[15,20] starts — ties the peak, does not beat it
20	−1	1	2	[15,20] ends
30	−1	0	2	[0,30] ends; active returns to 0

Answer 2 rooms.

• The interval identities are gone by the time the loop runs. After the events are built, nothing knows that [5,10] and [15,20] were different meetings — only that the timeline gains and loses occupants. That erasure is the whole trick: an interval problem becomes a running sum.
• active returns to exactly 0, which is a free correctness check. If it does not, the events are unbalanced — usually a missing -1 push, or a duplicate.
• best is not the last value, it is the maximum along the way. The peak at t=5 has passed by the time the scan finishes. Returning active instead of best returns 0 on every balanced input — a bug that looks like “my answer is always zero”.
• The touching case is where the tie-break earns its keep. On [[1,5],[5,9]] the events at t=5 are (5, -1) and (5, +1); Python sorts tuples lexicographically and −1 < 1, so the departure is processed first and the answer is 1. Push the release to end + 1 instead — the inclusive convention — and the same input answers 2. Both are right; which one the problem wants is a reading-comprehension question, not an algorithmic one.

Complexity

Step	Cost
Build $2n$ events	$O(n)$
Sort them	$O(n \log n)$ — dominates
Single pass	$O(n)$
Space	$O(n)$ for the event list
Total	$O(n \log n)$ time, $O(n)$ space

Formulation	Time	Space	When it wins
Two sorted arrays (starts, ends, two pointers)	$O(n \log n)$	$O(n)$	same bound, avoids building tuples; the classic LC 253 answer
Event list (this page)	$O(n \log n)$	$O(n)$	generalises to weighted deltas and to more than two event kinds
Min-heap of end times	$O(n \log n)$	$O(k)$ for k rooms	when you must also know which room, or track per-room state
Difference array / bucket counts	$O(n + T)$	$O(T)$	when times are small bounded integers ($T$ range) — beats sorting outright
Pairwise overlap check	$O(n^2)$	$O(1)$	never, beyond n < 100

The difference-array row is worth remembering: if timestamps are small integers — hours in a day, years in a range, coordinates up to $10^5$ — you can skip the sort entirely. Add +1 at start and −1 at end in an array of that size and prefix-sum it, which is $O(n + T)$ and often the intended solution for the “car pooling” and “corporate flight bookings” family (LC 1094, LC 1109). That is the same difference-array idea, and a sweep line is its unbounded-coordinates cousin.

The variant map

Variant	The event transform	Canonical problem
Peak overlap / min rooms	+1 at start, -1 at end	253 Meeting Rooms II
Weighted capacity	+n and -n instead of ±1	1094 Car Pooling
Inclusive endpoints	Release at end + 1	2406 Divide Intervals
Booking with a limit	Sweep on each query, or keep a delta map	731 · 732
Height profile	Sweep x-coordinates with a max-heap of heights	218 Skyline
Free time across schedules	Sweep for gaps where active == 0	759 (Premium)

Practice — real LeetCode problems

LC 1094 — Car Pooling · Medium

Problem. A car with capacity empty seats drives east only. Given trips[i] = [numPassengers, from, to], return True if it is possible to pick up and drop off all passengers without ever exceeding capacity.

Constraints. 1 <= len(trips) <= 1000, 1 <= numPassengers <= 100, 0 <= from < to <= 1000, 1 <= capacity <= 10^5.

Examples. trips = [[2,1,5],[3,3,7]], capacity = 4 gives False · same trips with capacity = 5 gives True

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The only change from the basic template is that events carry a weight (numPassengers) rather than ±1. The rolling sum is then occupancy rather than a count.

Time $O(n \log n)$. Space $O(n)$.

The third test case, [[2,1,5],[3,5,7]] with capacity 3, is the one that matters: trip 1 carries 2 passengers to location 5, and trip 2 picks up 3 at location 5. If the pickup were processed first, occupancy would momentarily hit 5 and wrongly return False. Because (5, -2) sorts before (5, 3), the drop-off happens first and the answer is correctly True.

Since locations are bounded by 1000, there is an even simpler $O(n + 1000)$ answer worth mentioning — a difference array over positions:

python

delta = [0] * 1001
for num, start, end in trips:
    delta[start] += num
    delta[end] -= num
onboard = 0
for d in delta:
    onboard += d
    if onboard > capacity:
        return False
return True

No sorting at all. This is the same relationship as prefix sums and difference arrays — when the coordinate space is small and bounded, bucket it directly instead of sorting events. Recognising that from the to <= 1000 constraint is the kind of thing that reads well.

Follow-ups you should expect: “What if the car could go both ways?” — the timeline no longer orders the trips, so the sweep breaks. “Coordinates up to $10^9$?” — the difference array dies, the event sweep survives. “Return the location of peak occupancy?” — record the timestamp when best updates.

LC 2406 — Divide Intervals Into Minimum Number of Groups · Medium

Problem. Given intervals[i] = [left, right] (both endpoints inclusive), split them into the minimum number of groups such that no two intervals in the same group intersect. Return that minimum.

Constraints. 1 <= len(intervals) <= 10^5, 1 <= left <= right <= 10^6.

Examples. [[5,10],[6,8],[1,5],[2,3],[1,10]] gives 3 · [[1,3],[5,6],[8,10],[11,13]] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Two intervals can share a group exactly when they do not intersect, so the minimum number of groups is the peak overlap — the argument in the note above.

Time $O(n \log n)$. Space $O(n)$.

The whole problem is the endpoint convention. These intervals are inclusive: [1,5] occupies position 5, so it conflicts with [5,10]. Emitting (end, -1) would let the release sort before the arrival and count them as compatible — returning 2 instead of 3 on the first example. Releasing at end + 1 keeps the interval active through end.

[[1,2],[2,3]] returning 2 is the minimal test of this: with half-open handling it would wrongly give 1.

Follow-ups you should expect: “Which intervals go in which group?” — use the min-heap formulation; the heap slot you reuse identifies the group. “Coordinates up to $10^6$ — use a difference array?” — yes, $O(n + 10^6)$, a reasonable trade at this size and the same insight as LC 1094. “Are the groups unique?” — no, only the count is; many valid partitions exist.

LC 253 — Meeting Rooms II · Medium · Premium

Problem. Given meeting time intervals [start, end), return the minimum number of conference rooms required.

Examples. [[0,30],[5,10],[15,20]] gives 2 · [[7,10],[2,4]] gives 1

This one is Premium on LeetCode

LC 253 sits behind LeetCode’s paywall, so you may not be able to submit against the real judge. It is included because it is the canonical statement of this pattern and is asked constantly. The exercise below runs locally, and LC 2406 is the free problem that asks the same question with inclusive endpoints.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The answer is the peak overlap, for the lower-bound/upper-bound reason given earlier: k simultaneous meetings need k rooms, and k rooms always suffice.

Time $O(n \log n)$. Space $O(n)$.

[[1,5],[5,10],[10,15]] returning 1 is the half-open test: consecutive back-to-back meetings share one room. Contrast with LC 2406, where the same shape of input gives 2 because endpoints are inclusive. Same pattern, opposite convention — which is exactly why “are the endpoints inclusive?” is a genuine clarifying question rather than pedantry.

The empty-input case returning 0 is worth a guard in the heap version (intervals[0] would raise); the event version handles it naturally since the loop simply never runs.

Follow-ups you should expect: “Which room does each meeting get?” — the heap version: pair each end time with a room id, and reuse the popped id. “Meeting Rooms I (LC 252)?” — just whether any two overlap: sort by start and check adjacent pairs, or ask whether the peak exceeds 1. “What if rooms have capacities or features?” — no longer a pure sweep; becomes a matching or flow problem. “Return the busiest time window?” — track the timestamps where active hits best.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 218 is the sweep line’s final form

The Skyline Problem sweeps x-coordinates while maintaining a max-heap of the heights of currently active buildings. At each event the current skyline height is the heap’s maximum; whenever that maximum changes, you emit a key point.

It combines this page’s event transform with the lazy-deletion technique from Two Heaps, since buildings expire and heaps cannot remove arbitrary elements. If you can build it from those two pieces rather than memorising it, you understand both patterns.

7 problems

0 easy4 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○253Meeting Rooms IIpremiummediumThe canonical statement; half-open endpointsNeetCode 150Blind 75
• ○731My Calendar IImediumAllow double booking, reject triple -- sweep a delta map per query
• ○1094Car PoolingmediumWeighted events; bounded coordinates allow a difference array
• ○2406Divide Intervals Into Minimum Number of Groupsmedium**Inclusive** endpoints -- release at `end + 1`
• ○218The Skyline ProblemhardSweep x-coordinates with a max-heap of active heights
• ○732My Calendar IIIhardReturn the running peak after each booking; a `SortedDict` of deltas
• ○759Employee Free TimepremiumhardSweep for the gaps where `active == 0`

Interview follow-ups

They ask	What they’re checking	The answer
“Are the endpoints inclusive?”	Whether you ask it	It flips the tie-break: half-open means touching is fine; inclusive means release at end + 1
“Why does minimum rooms equal peak overlap?”	Rigour	k simultaneous meetings force k rooms (lower bound), and k rooms always suffice by assigning greedily (upper bound)
“Sweep or heap?”	Judgement	Same $O(n \log n)$; events generalise to weights and profiles, the heap tells you which resource is reused
“Coordinates are small and bounded”	Recognising the shortcut	A difference array over positions gives $O(n + \text{range})$ with no sorting
“Coordinates up to $10^9$?”	The reverse	The difference array dies; the event sweep is unaffected
“Why do drop-offs sort before pickups?”	Attention to detail	Tuple comparison: (t, -1) < (t, 1) because -1 < 1 — the correct behaviour falls out for free
“Can you stream the intervals?”	Limits	A sweep needs all events sorted up front; for online queries keep a sorted delta map (LC 731/732)

Edge-case checklist

• Empty input — must return 0; the event version handles it, the heap version needs a guard.
• Single interval — answer 1.
• Touching intervals — [[1,5],[5,10]]; the case that exposes the endpoint convention. Half-open gives 1, inclusive gives 2.
• Fully nested intervals — [[1,10],[2,9],[3,8]] gives 3; overlap is not just about crossing edges.
• Identical intervals — n copies overlap n times.
• Zero-length interval — [[1,1]]; sane under inclusive endpoints, degenerate under half-open.
• All disjoint — answer 1, verifying you take a maximum rather than a total.
• Unsorted input — always sort; never assume the input is ordered.

Self-check

pch.quizTag Sweep line — self-check

1. What does converting intervals into (time, ±1) events actually buy you?

   A It sorts faster than sorting intervals B It discards interval identity and turns the problem into a running sum over a timeline — so 'how many overlap' becomes a prefix maximum rather than a pairwise comparison C It removes the need to sort D It handles unsorted input automatically
   pch.quizShowAnswer

   B — It discards interval identity and turns the problem into a running sum over a timeline — so 'how many overlap' becomes a prefix maximum rather than a pairwise comparison — After the events are built, nothing knows which meeting was which. That erasure is exactly what collapses an O(n²) pairwise question into one O(n) pass.

2. Two intervals touch: one ends at 5, another starts at 5. Do they overlap?

   A Always yes B It depends on the convention — half-open [start, end) means no (the template's (5,−1) sorts before (5,+1), so the room frees first), while inclusive [start, end] means yes, which requires pushing the release to end + 1 C Always no D Only if a third interval is present
   pch.quizShowAnswer

   B — It depends on the convention — half-open [start, end) means no (the template's (5,−1) sorts before (5,+1), so the room frees first), while inclusive [start, end] means yes, which requires pushing the release to end + 1 — On [[1,5],[5,9]] the half-open reading answers 1 and the inclusive reading answers 2. Both are correct algorithms; which the problem wants is a reading question, and getting it backwards is the classic sweep-line bug.

3. Why does the template return `best` rather than `active`?

   A They are the same at the end B Because `active` is 0 at the end of any balanced input — the peak occurred earlier in the scan, so it must be tracked as a running maximum C Because `active` can go negative D Because `best` is faster to compute
   pch.quizShowAnswer

   B — Because `active` is 0 at the end of any balanced input — the peak occurred earlier in the scan, so it must be tracked as a running maximum — Returning `active` gives 0 on every valid input, which presents as 'my answer is always zero'. That `active` lands back on 0 is also a free correctness check for unbalanced events.

4. Timestamps are guaranteed to be integers from 0 to 1000. What is the better solution?

   A The same event sort — O(n log n) is optimal B A difference array of size 1001: +1 at start, −1 at end, then prefix-sum. O(n + T) with no sort at all C A min-heap of end times D Binary search over the answer
   pch.quizShowAnswer

   B — A difference array of size 1001: +1 at start, −1 at end, then prefix-sum. O(n + T) with no sort at all — This is the intended solution for the car-pooling and flight-booking family (LC 1094, LC 1109). A sweep line is the version you fall back to when coordinates are unbounded.

5. When is the min-heap-of-end-times formulation preferable to the event list?

   A It is always faster B When you need more than the count — which room a meeting got, or per-room state — since the heap keeps the rooms themselves rather than just a total C When intervals are sorted D When there are more than 10^6 intervals
   pch.quizShowAnswer

   B — When you need more than the count — which room a meeting got, or per-room state — since the heap keeps the rooms themselves rather than just a total — Both are O(n log n). The event list generalises better to weighted deltas and extra event types; the heap generalises better when you must identify the resource.

6. The problem asks for the total time covered by at least one interval, not the peak count. What changes?

   A Nothing B Track the previous event time and accumulate (t − prev) whenever `active > 0` before applying the delta — the sweep is the same, the accumulator changes C Sort by end time instead D Use the greedy interval-scheduling template
   pch.quizShowAnswer

   B — Track the previous event time and accumulate (t − prev) whenever `active > 0` before applying the delta — the sweep is the same, the accumulator changes — Same events, different thing measured between them. Recognising that the sweep is a framework — count, coverage, weighted load — rather than one recipe is the transferable part.

Recall card

• Cue — “how many overlap at once”, “minimum rooms/platforms/servers”, “peak load”, or anything asking about a quantity over time rather than which intervals to pick.
• Do — emit (start, +1) and (end, -1) for every interval, sort, then scan a running active, tracking best = max(best, active).
• Return best, not active — active ends at 0 on balanced input.
• The tie-break is the bug — half-open [s, e): (t,-1) sorts before (t,+1) for free, so touching intervals do not conflict. Inclusive [s, e]: push the release to end + 1.
• active back to 0 at the end is a free sanity check.
• Cost — $O(n \log n)$ time from the sort, $O(n)$ space.
• Small integer timestamps → skip the sort: a difference array plus prefix sum is $O(n + T)$ (LC 1094, LC 1109).
• Heap variant when you need which resource, not just how many.
• Not the same as greedy selection — that picks a subset, this measures the timeline.

Recap

• Turn each interval into two events: +1 at start, -1 at end. Sort, scan, keep a running total — that total is the live overlap.
• Minimum rooms/groups = peak overlap. Be ready to prove both bounds.
• The tie-break is the pattern’s one real subtlety. Half-open intervals work for free because (t, -1) sorts before (t, 1). Inclusive endpoints need end + 1.
• Events carry weights just as easily as ±1 (LC 1094).
• When coordinates are small and bounded, a difference array skips the sort entirely — $O(n + \text{range})$.
• A min-heap of end times is the equivalent formulation, and is better when you need to know which resource is reused.
• Merging intervals outputs intervals; sweeping outputs a count. Choose by what the answer looks like.

Next: Greedy Interval Scheduling — why sorting by end time is the right move when you want to keep as many intervals as possible.