Sweep Line
Why sweep line exists — the story
You're an SRE at Uber. Every ride creates a driver_online event at time t_start and a driver_offline event at time t_end. Your dashboard shows: "How many drivers are on the road at any moment during the peak-hour surge?"
The obvious approach: for every timestamp in the surge window, count how many [t_start, t_end] ranges contain it. With 100,000 drivers and one query per second, that's 10⁵ interval-containment checks per query × 3600 queries per hour = 3.6·10⁸ ops per hour. Doable for one dashboard. But now imagine a company like Uber with 200 cities, each running this analytic, and you're at 7·10¹⁰ ops per hour. Fleet dies.
And the naive approach re-does work. When time advances from 12:00:00 to 12:00:01, the driver count changes by at most a handful — someone came online, someone finished a ride. Yet the naive scan asks the question from scratch on every second. Every one of those 100,000 checks is unchanged from the previous second.
The pattern is sweep line: turn intervals into a stream of events. A driver_online event is +1. A driver_offline is −1. Sort all events by time. Scan left to right, maintaining a running active counter. Now the "how many drivers online at time t" query is just: read the counter after processing events up to time t. O(n log n) sort + O(n) scan, answers every time-point query in the surge window in a single pass. 3.6·10⁸ ops per hour → about 2·10⁵. Four orders of magnitude faster.
The pattern gets its name from geometry: imagine a vertical line sweeping across a drawing from left to right. Whenever the line hits the start or end of an interval, your state changes. For meeting rooms the state is a count. For car pooling it is passengers in the car. For skyline it is a max-heap of active building heights. The reusable idea is always the same: sort the moments where state can change, then process them in order.
For the meeting-rooms flavour of this: meetings scheduled as [0,30], [5,10], [15,20]. Events: (0,+1), (30,-1), (5,+1), (10,-1), (15,+1), (20,-1). Sort by time: active becomes 1 at time 0, 2 at time 5, back to 1 at time 10, 2 at time 15, 1 at time 20, 0 at time 30. Peak active is 2 → two rooms.
Same input, different lens. Merge Intervals asks "which intervals overlap into which?"; sweep line asks "how many are active at time t?". The +1/−1 event stream answers the second in one linear pass.
active count. The maximum value in that row is 2, so two meetings overlap at peak and two rooms are required.At every event time t, active = Σ (+1 for starts ≤ t) − Σ (+1 for ends ≤ t). The running counter is the answer to "how many are active at this instant." Sanity check: active must be ≥ 0 at all times; a negative value means an end event fired without a matching start (data corruption).
Meetings [1,5] and [5,10]: does the end at 5 fire before or after the start at 5? Answer changes the room count. The rule for "sharing endpoints doesn't need a new room": sort so that end events precede start events on ties. In Java: Arrays.sort(events, (a, b) -> a.time != b.time ? a.time - b.time : a.type - b.type) where type = 0 for end, 1 for start.
The sweep produces the same peak whether you use +1 at start / −1 at (end + 1) OR +1 at start / −1 at end with the tie-break rule above. Pick one convention and stick to it. Mixing conventions across problems is the single most common sweep-line bug.
When to use it — and when not to
Recognize by
- peak concurrency — "minimum meeting rooms", "maximum number of active sessions", "busiest moment".
- total coverage / uncovered gap on a number line.
- "can capacity ever be exceeded?" — passenger count, CPU load, bandwidth, reservations.
- "timeline of changes" — starts add something, ends remove something.
- "skyline" — max height at every x-coordinate (event = building start/end).
- many intervals where only endpoints matter; nothing changes inside an interval.
When NOT to use it
You need to reconstruct which intervals were merged rather than count activity. Use Merge Intervals instead. Also, if events arrive online (no chance to sort up front), reach for a TreeMap or segment tree instead of an event-array sweep.
Also avoid the plain event sweep when:
- intervals are not known in advance and you need instant answers after each insertion.
- the query asks for membership of specific original intervals, not aggregate state.
- coordinates are huge but sparse and you accidentally allocate an array over the coordinate range.
- endpoints have ambiguous inclusivity; decide whether
[1,5]and[5,10]overlap before coding. - state cannot be updated by a simple add/remove; you may need a heap, multiset, or segment tree as the swept state.
How to use it — template
List<int[]> events = new ArrayList<>();
for (int[] in : intervals) {
events.add(new int[]{in[0], +1}); // opening event
events.add(new int[]{in[1], -1}); // closing event
}
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int active = 0, best = 0;
for (int[] e : events) {
active += e[1];
best = Math.max(best, active);
}
return best;The first loop turns intervals into the only moments that matter: starts and ends. The sort creates the left-to-right sweep order. The tie-break is part of the problem definition: with -1 before +1, a meeting ending at 5 frees the room before another meeting starting at 5 asks for one. The scan keeps the current aggregate in active and records whatever the problem asks for — maximum, total covered length, first overload, or a list of output segments.
Sweep-line flavors you should name out loud
Not every sweep line uses the same state. Before coding, decide which flavor you are in:
| Flavor | State carried while sweeping | Example question |
|---|---|---|
| Count sweep | active += delta | How many rooms/platforms are needed? |
| Weighted sweep | load += passengers | Does car pooling exceed capacity? |
| Coverage sweep | previous coordinate + active count | How many total units are covered by at least one interval? |
| Extremum sweep | heap or multiset of active values | What is the skyline height at each x? |
For coverage length, the scan records distance, not just state. If the previous coordinate was prev and current coordinate is x, then the segment [prev, x) had whatever active count you carried from the last event. If active > 0, add x - prev to covered length. Then apply all events at x. This tiny ordering detail is why sweep line feels subtle at first: the state between events describes the open segment after the previous coordinate, not the point itself.
Tie-breaks are part of the problem
At equal coordinates, you must know whether an end and a start overlap. For meetings, [1,5] followed by [5,10] usually uses one room, so process the end before the start. For closed intervals where both endpoints count, touching intervals do overlap, so you may process starts before ends or shift end events by one in integer-coordinate problems. For skyline, starts and ends at the same x need special ordering by height so the silhouette does not briefly dip or spike. Do not treat the comparator as boilerplate; it encodes the interval semantics.
History — Bentley-Ottmann sweep, 1979
The sweep-line technique was formalized by Jon Bentley and Thomas Ottmann in 1979 for the classical problem of finding all intersection points among n line segments in a 2D plane. Their algorithm sweeps a vertical line from left to right, maintaining a binary search tree of active segments ordered by their y-coordinate at the sweep line. When a segment starts, it's inserted; when it ends, it's removed; segment intersections happen precisely when adjacent segments in the BST swap order. Total complexity: O((n + k) log n) where k is the number of intersections — a huge win over the naive O(n²) brute force.
The idea generalized beyond geometry. Franco Preparata and Michael Shamos's foundational textbook Computational Geometry (1985) devoted an entire chapter to the pattern. Modern applications:
- CAD software (AutoCAD, Fusion 360) sweeps to detect overlapping boundaries in real time as you draw.
- Chip design (VLSI CAD) uses sweep to check for design-rule violations (are these two metal traces too close?) on billion-transistor circuits.
- Graphics engines use "z-buffer sweeps" to determine which pixels are covered by which triangles.
- Databases use interval-tree-like sweeps to compute date-range JOINs efficiently.
- Every "meeting rooms" / "concurrent sessions" / "peak users" question on LeetCode is a 1D sweep. The 2D Bentley-Ottmann is where the pattern's name comes from.
The "sweep as an event-processing metaphor" was originally "a vertical line moving from left to right" in Bentley's language. Today it's the mental model behind every event-driven state machine.
Meeting Rooms II (Minimum Concurrent Intervals) Medium
Problem
Given meeting time intervals, find the minimum number of rooms so that no two overlapping meetings share a room.
Constraints: 1 ≤ n ≤ 10⁴; start < end.
Example 1: [[0,30],[5,10],[15,20]] → 2.
Example 2: [[7,10],[2,4]] → 1 because the meetings do not overlap.
Solution — brute force
A direct baseline checks every interesting time and counts how many intervals cover it.
// Pseudocode baseline:
// best = 0
// for each meeting m as a candidate time:
// active = number of intervals with interval.start <= m.start < interval.end
// best = max(best, active)You only need to test meeting start times because the active count can increase only when a meeting starts. This still takes O(n²): for each of n starts, scan all n intervals. Sweep line compresses those repeated counts into one sorted event stream.
best = 0
for each meeting start t:
active = 0
for each interval [s, e):
if s <= t < e:
active++
best = max(best, active)
return bestBrute force complexity: O(n²) time and O(1) extra space.
Solution — optimized
Either a min-heap of end times or a sweep of +1/−1 events. Both compute the peak number of simultaneously active intervals.
You need a new room only when the earliest-ending active meeting hasn't finished before the next starts. The heap top is that earliest end; reuse the room if it's free.
After sorting all start(+1)/end(−1) events by time, the running sum equals the number of active meetings at that instant; the maximum is the room count.
Java (heap)
int minMeetingRooms(int[][] meetings) {
Arrays.sort(meetings, (a, b) -> a[0] - b[0]); // by start
PriorityQueue<Integer> ends = new PriorityQueue<>(); // min-heap of end times
for (int[] m : meetings) {
if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll(); // room freed
ends.offer(m[1]);
}
return ends.size();
}heap version on [[0,30],[5,10],[15,20]].
int minMeetingRoomsSweep(int[][] meetings) {
int n = meetings.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
Arrays.sort(starts); Arrays.sort(ends);
int rooms = 0, best = 0, i = 0, j = 0;
while (i < n) {
if (starts[i] < ends[j]) { rooms++; i++; best = Math.max(best, rooms); }
else { rooms--; j++; } // a meeting ended: free a room
}
return best;
}two-array sweep on starts [0,5,15] and ends [10,20,30].
Space Complexity
Space O(n). The heap can hold active meeting ends, and the two-array sweep stores all starts and ends.
Learning notes
- Why store starts and ends separately? — it turns overlap counting into two sorted event streams.
- Why
starts[i] < ends[j]? — equal time means a room frees before the next meeting starts. - Why increment
roomson a start? — a new active meeting needs capacity right now. - Why decrement on an end? — that meeting no longer occupies a room.
- Why track
bestinstead of returning current rooms? — the answer is the peak concurrency over the whole sweep. - Why a min-heap alternative? — the smallest end time tells whether the earliest room is reusable.
Additional notes:
Time O(n log n) · Space O(n). The sort dominates. The heap version stores active room end times; the sweep version stores starts and ends.
Tie at start == end. Example: meetings [1,5] and [5,10]. If end-events sort before start-events, one room suffices (release, then acquire). If start sorts first, you need 2. LeetCode's Meeting Rooms II treats them as one — sort ends first on ties.
First, I'd clarify whether a meeting ending at time t frees a room for another starting at t; here it does. The brute force is to count active intervals at every start time, which is O(n²). To optimize, I can either sort starts and ends as events or keep a min-heap of active end times. Both are O(n log n); the sweep makes the peak-concurrency idea especially explicit.
Peak-concurrency sweep also solves Car Pooling, Minimum Number of Platforms, and (with a heap keyed on height) The Skyline Problem.
Sweep Line — the general recipe
What & why: the event-sorting template behind interval and scheduling problems. Goal — turn any "how many overlap / when is it busiest" question into a sorted stream of +1/−1 events you scan once.
For any "at each coordinate, what is the aggregate of intervals covering it?" problem:
1. Emit events: (start, +delta) and (end, -delta).
2. Sort events by coordinate; break ties so closings that free capacity
are processed before openings when intervals touching should not overlap.
3. Sweep left to right, maintaining a running aggregate (count / sum / heap).
4. Record the aggregate (max, or per-segment) as you pass each coordinate.Sweep line converts a 2D "which intervals overlap here" question into a 1D ordered event stream. The state you carry (counter, sum, or a heap of active heights) defines the problem.
Choosing the swept state
A counter is enough when every interval contributes the same +1 while active. A running sum handles weighted intervals, like passengers in a car or CPU load from jobs. A heap or multiset is needed when you need the maximum active value, such as skyline height. A TreeMap of deltas is the online-friendly version: insert +delta and -delta as bookings arrive, then scan the ordered map to answer overlap.
Endpoint policy
Most sweep bugs are endpoint bugs. Decide if intervals are half-open [start,end) or closed [start,end]. Meeting rooms usually behave like half-open intervals: a meeting ending at 10 does not overlap one starting at 10. Calendar booking problems may define overlap differently. Once you decide, encode it in the tie-break. For half-open counting, process end before start at the same coordinate.
Online sweep with TreeMap
If the intervals arrive one booking at a time, you cannot sort a fresh event array after every call unless the constraints are tiny. The same idea becomes a difference map: add +1 at start, add -1 at end, then scan keys in order to compute the max prefix sum. This is how the My Calendar family is usually introduced. The map stores only coordinates where something changes, so it avoids allocating a giant timeline.
The trade-off is that each query may still scan many keys unless you maintain extra segment-tree information. That distinction is useful in interviews: an event array is best for batch input; a TreeMap delta structure is best for moderate online input; a segment tree is for large online input with many queries.
Coverage example by hand
For intervals [1,4] and [2,6] as half-open ranges, events are (1,+1), (4,-1), (2,+1), (6,-1). Sweep sorted coordinates 1,2,4,6. From 1 to 2, active is 1, so length 1 is covered. From 2 to 4, active is 2, so length 2 is covered. From 4 to 6, active is 1, so length 2 is covered. Total covered length is 5, representing [1,6). Notice we never asked which interval owns each point; the active count was enough.
First, I'd convert the intervals into events because the active count changes only at endpoints. Then I'd sort the events, explicitly defining the tie-break for equal times. As I sweep left to right, the running count is the number of active intervals, and the maximum is the rooms needed. The brute force is O(n²); sorting events gives O(n log n) time and O(n) space.
Brute force to optimized, in one mental move
The brute force asks, "for this time, how many intervals contain it?" Sweep line asks the same question for every time in sorted order, while carrying the answer forward. Between two adjacent event times, the active set cannot change, so there is no reason to rescan all intervals. This is the core optimization: replace repeated membership checks with incremental state updates.
Debugging checklist
When a sweep solution is off by one room or one unit of coverage, check these in order: Are end events ordered before start events for half-open intervals? Are multiple events at the same coordinate grouped or at least processed with the correct tie-break? Are you recording the answer before or after applying the event? Are you using coordinate compression or a map instead of allocating an array from 0 to 10^9? Most sweep bugs live in those four questions, not in the loop itself.
With a TreeMap as the event/difference structure, sweep handles My Calendar I/II/III (max booking overlap) online. With a max-heap of active building heights, it yields the skyline silhouette.
Same pattern, new tweaks
"Turn intervals into +1/−1 events and track the running count" measures peak overlap everywhere:
| Variation | The one thing that changes |
|---|---|
| Car Pooling | +passengers at pickup, −passengers at drop-off; fail as soon as the running load exceeds capacity. |
| Minimum Number of Platforms | Train arrival/departure times are just meeting starts/ends with railway names. |
| My Calendar II / III | Use a TreeMap of deltas because bookings arrive one at a time. |
| The Skyline Problem | Events add/remove building heights; the swept state is a max-heap or multiset, not a count. |
| Employee Free Time | Sweep all busy intervals and record gaps where the active count is zero. |