- API Kernel:
LineSweep - Why Line Sweep?
- Core Insight
- Universal Template Structure
- Event Encoding Strategies
- State Management Data Structures
- Pattern Variants
- Problem: Meeting Rooms II (LC 253)
- Problem: Car Pooling (LC 1094)
- Problem: The Skyline Problem (LC 218)
- Pattern Comparison
- When to Use Each Pattern
- Data Structure Selection
- Complexity Comparison
- When to Use Line Sweep
- Quick Reference Templates
- Event Encoding Cheat Sheet
Core Mechanism: Transform intervals/rectangles into discrete events (start/end points), sort by position, and sweep through maintaining state with a data structure.
Line sweep solves problems where:
- You have multiple overlapping intervals, rectangles, or ranges
- You need to track aggregate state (count, max height, capacity) at any point
- Processing all pairs would be O(n²) but events can be processed in O(n log n)
Every interval creates two events: a start event and an end event. By processing events in sorted order, we convert a 2D overlap problem into a 1D scan.
Intervals: [1,4] [2,5] [3,6]
Events: 1:+1 2:+1 3:+1 4:-1 5:-1 6:-1
↓ ↓ ↓ ↓ ↓ ↓
Count: 1 2 3 2 1 0
Max = 3 (at position 3)
def line_sweep(intervals):
# Step 1: Create events
events = []
for start, end in intervals:
events.append((start, +1)) # Start event
events.append((end, -1)) # End event
# Step 2: Sort events
# Tie-breaking rule depends on problem:
# - For counting overlap: end before start at same position
# - For skyline: start before end at same position
events.sort()
# Step 3: Sweep and maintain state
current_state = 0
result = initial_value
for position, delta in events:
current_state += delta
result = update(result, current_state)
return result| Problem Type | Start Event | End Event | Sort Key | Tie-breaking |
|---|---|---|---|---|
| Count Overlap | (pos, +1) | (pos, -1) | position | end before start |
| Skyline | (pos, -height) | (pos, height) | position | start before end |
| Capacity Check | (pos, +load) | (pos, -load) | position | depends on semantics |
| Complexity | Data Structure | Use Case |
|---|---|---|
| Simple counting | Integer counter | Meeting rooms, car pooling |
| Max tracking | Heap or Sorted Container | Skyline problem |
| Complex queries | Segment Tree | Range-based queries |
- Event Counting (Base): Count active intervals at each point
- Capacity Tracking: Track cumulative load/capacity
- Height Tracking: Maintain max height with multiset/heap
- Difference Array: Offline version using prefix sums
Base Template for event counting line sweep.
Given an array of meeting time intervals [[start, end], ...], find the minimum number of conference rooms required.
Invariant: At any point, track the number of ongoing meetings.
Key Insight: Maximum concurrent meetings = minimum rooms needed.
Meetings: [[0,30], [5,10], [15,20]]
Events (sorted):
0: +1 (start) → count = 1
5: +1 (start) → count = 2 ← max
10: -1 (end) → count = 1
15: +1 (start) → count = 2 ← max
20: -1 (end) → count = 1
30: -1 (end) → count = 0
Answer: 2 rooms
def minMeetingRooms(intervals: list[list[int]]) -> int:
events = []
for start, end in intervals:
events.append((start, 1)) # Meeting starts
events.append((end, -1)) # Meeting ends
# Sort: by time, then ends before starts at same time
events.sort(key=lambda x: (x[0], x[1]))
max_rooms = 0
current_rooms = 0
for _, delta in events:
current_rooms += delta
max_rooms = max(max_rooms, current_rooms)
return max_roomsWhen a meeting ends and another starts at the same time, we can reuse the room:
- Process end (-1) first to free the room
- Then process start (+1) to occupy it
Sort key (time, delta) achieves this since -1 < +1.
- Time: O(n log n) for sorting
- Space: O(n) for events array
import heapq
def minMeetingRooms_heap(intervals: list[list[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # Sort by start time
heap = [] # Min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap) # Reuse room
heapq.heappush(heap, end)
return len(heap)Both approaches are O(n log n), but line sweep generalizes better.
Variant: Capacity tracking with line sweep.
Given trips = [[numPassengers, from, to], ...] and capacity, determine if it's possible to pick up and drop off all passengers without exceeding capacity.
Invariant: At any point, current passengers ≤ capacity.
Delta from Base: Events have variable weights (passenger count), not just ±1.
trips: [[2,1,5], [3,3,7]], capacity = 4
Events (sorted):
1: +2 (pickup) → passengers = 2 ≤ 4 ✓
3: +3 (pickup) → passengers = 5 > 4 ✗
5: -2 (dropoff) → passengers = 3
7: -3 (dropoff) → passengers = 0
Answer: False (exceeded at position 3)
def carPooling(trips: list[list[int]], capacity: int) -> bool:
events = []
for passengers, start, end in trips:
events.append((start, passengers)) # Pickup
events.append((end, -passengers)) # Dropoff
# Sort: by position, then dropoffs before pickups at same position
events.sort(key=lambda x: (x[0], x[1]))
current_passengers = 0
for _, delta in events:
current_passengers += delta
if current_passengers > capacity:
return False
return TrueAt the same position, passengers exit before new ones board:
- Process dropoff (negative delta) first
- Then process pickup (positive delta)
This is automatic with sort key (position, delta) since negative < positive.
When positions are bounded and small:
def carPooling_diff(trips: list[list[int]], capacity: int) -> bool:
# Positions bounded by 0 to 1000
diff = [0] * 1001
for passengers, start, end in trips:
diff[start] += passengers
diff[end] -= passengers
current = 0
for delta in diff:
current += delta
if current > capacity:
return False
return TrueTrade-off: O(max_position) space but O(n + max_position) time (no sorting).
- Line Sweep: O(n log n) time, O(n) space
- Difference Array: O(n + P) time, O(P) space where P = max position
| Aspect | Meeting Rooms II | Car Pooling |
|---|---|---|
| Delta | Always ±1 | Variable (passenger count) |
| Goal | Find maximum | Check threshold |
| Return | Count | Boolean |
Advanced Variant: Height tracking with multiset/heap.
Given buildings [[left, right, height], ...], return the skyline as a list of key points [[x, height], ...] where the silhouette changes.
Invariant: Track maximum height among all active buildings at each position.
Delta from Base: Instead of counting, maintain a multiset of active heights.
Buildings: [[2,9,10], [3,7,15], [5,12,12]]
Events:
x=2: add height 10 → max = 10 → output [2, 10]
x=3: add height 15 → max = 15 → output [3, 15]
x=5: add height 12 → max = 15 (no change)
x=7: remove height 15 → max = 12 → output [7, 12]
x=9: remove height 10 → max = 12 (no change)
x=12: remove height 12 → max = 0 → output [12, 0]
Skyline: [[2,10], [3,15], [7,12], [12,0]]
from sortedcontainers import SortedList
def getSkyline(buildings: list[list[int]]) -> list[list[int]]:
# Create events: (x, type, height)
# type: 0 = start (add), 1 = end (remove)
events = []
for left, right, height in buildings:
events.append((left, 0, height)) # Building starts
events.append((right, 1, height)) # Building ends
# Sort: by x, then starts before ends, then by height (desc for starts)
events.sort(key=lambda e: (e[0], e[1], -e[2] if e[1] == 0 else e[2]))
result = []
active_heights = SortedList([0]) # Always include ground level
for x, event_type, height in events:
if event_type == 0: # Start
active_heights.add(height)
else: # End
active_heights.remove(height)
current_max = active_heights[-1]
# Only add point if max height changed
if not result or result[-1][1] != current_max:
result.append([x, current_max])
return resultimport heapq
def getSkyline_heap(buildings: list[list[int]]) -> list[list[int]]:
events = []
for left, right, height in buildings:
events.append((left, -height, right)) # Start: negative height for max-heap
events.append((right, 0, 0)) # End: height 0 as marker
events.sort()
result = []
# Max-heap: (-height, end_x)
heap = [(0, float('inf'))] # Ground level
for x, neg_height, end_x in events:
# Lazy deletion: remove buildings that have ended
while heap[0][1] <= x:
heapq.heappop(heap)
if neg_height: # Start event
heapq.heappush(heap, (neg_height, end_x))
current_max = -heap[0][0]
if not result or result[-1][1] != current_max:
result.append([x, current_max])
return resultFor skyline, the sort order is critical:
- Same x: Process starts before ends (so we see new max before removing old)
- Same x, same type:
- Starts: taller buildings first (higher height wins)
- Ends: shorter buildings first (delays height drop)
| Aspect | Meeting Rooms | Skyline |
|---|---|---|
| State | Simple counter | Max of active set |
| Operation | increment/decrement | insert/delete/find-max |
| Data Structure | Integer | Heap or Sorted Container |
| Output | Single value | List of critical points |
- Time: O(n log n) for sorting and heap/sorted container operations
- Space: O(n) for events and active buildings
- Buildings with same left edge: taller one determines skyline
- Buildings with same right edge: process in order
- Adjacent buildings: merge if same height
- Nested buildings: inner building doesn't affect outer skyline
| Problem | Event Type | State Structure | Output | Sort Tie-break |
|---|---|---|---|---|
| Meeting Rooms II | ±1 (start/end) | Integer counter | Max count | End before start |
| Car Pooling | ±passengers | Integer counter | Boolean | Dropoff before pickup |
| Skyline | add/remove height | Sorted container | Critical points | Starts before ends |
Need to track overlap count?
├── Yes → Event Counting (Meeting Rooms II)
│ └── Need capacity check instead of max?
│ └── Yes → Capacity Tracking (Car Pooling)
└── No → Need to track max height?
└── Yes → Height Tracking (Skyline)
| Requirement | Data Structure | Example |
|---|---|---|
| Count only | Integer | Meeting Rooms II |
| Count with threshold | Integer | Car Pooling |
| Max of active set | Heap or SortedList | Skyline |
| Range queries | Segment Tree | Complex variants |
| Problem | Time | Space | Key Operation |
|---|---|---|---|
| Meeting Rooms II | O(n log n) | O(n) | Counter update |
| Car Pooling | O(n log n) | O(n) | Counter check |
| Skyline | O(n log n) | O(n) | Max query + deletion |
Use line sweep when you see:
- Multiple intervals that can overlap
- Questions about overlap (count, max, capacity)
- Aggregate state at positions (how many active? max height?)
- Temporal or spatial ordering (sort by time/position makes sense)
Problem has intervals/ranges?
├── No → Not line sweep
└── Yes → What do you need to track?
├── Count of overlaps → Event Counting
│ └── Examples: Meeting Rooms II, Course Schedule III
├── Sum/capacity → Capacity Tracking
│ └── Examples: Car Pooling, Range Addition
└── Max/min of active set → Height Tracking
└── Examples: Skyline, Falling Squares
| Alternative | When to Prefer Alternative |
|---|---|
| Merge Intervals | Need to collapse overlapping intervals, not count them |
| Interval Scheduling | Greedy selection (maximize non-overlap) |
| Difference Array | Bounded positions, avoid sorting |
| Segment Tree | Complex range queries with updates |
| If problem says... | Think about... |
|---|---|
| "minimum rooms" | Event counting, find max |
| "can all fit" | Capacity tracking, check threshold |
| "silhouette/outline" | Height tracking with sorted container |
| "at any point in time" | Track state during sweep |
- Wrong tie-breaking: End before start vs start before end depends on semantics
- Off-by-one: Half-open intervals
[start, end)vs closed[start, end] - Missing ground level: Skyline needs height 0 as baseline
- Lazy deletion bugs: Heap approach requires careful cleanup
def max_overlap(intervals: list[list[int]]) -> int:
"""Find maximum number of overlapping intervals."""
events = []
for start, end in intervals:
events.append((start, 1)) # Start event
events.append((end, -1)) # End event
# Sort: by position, then ends before starts (for half-open intervals)
events.sort(key=lambda x: (x[0], x[1]))
max_count = current = 0
for _, delta in events:
current += delta
max_count = max(max_count, current)
return max_countdef can_fit_capacity(trips: list[tuple[int, int, int]], capacity: int) -> bool:
"""Check if all trips fit within capacity."""
events = []
for load, start, end in trips:
events.append((start, load)) # Add load
events.append((end, -load)) # Remove load
events.sort(key=lambda x: (x[0], x[1]))
current = 0
for _, delta in events:
current += delta
if current > capacity:
return False
return Truefrom sortedcontainers import SortedList
def skyline(buildings: list[list[int]]) -> list[list[int]]:
"""Get skyline critical points."""
events = []
for left, right, height in buildings:
events.append((left, 0, height)) # Start
events.append((right, 1, height)) # End
# Sort: by x, starts before ends, taller starts first
events.sort(key=lambda e: (e[0], e[1], -e[2] if e[1] == 0 else e[2]))
result = []
heights = SortedList([0])
for x, event_type, h in events:
if event_type == 0:
heights.add(h)
else:
heights.remove(h)
current_max = heights[-1]
if not result or result[-1][1] != current_max:
result.append([x, current_max])
return resultimport heapq
def skyline_heap(buildings: list[list[int]]) -> list[list[int]]:
"""Get skyline using heap with lazy deletion."""
events = []
for left, right, height in buildings:
events.append((left, -height, right)) # Start: negative for max-heap
events.append((right, 0, 0)) # End marker
events.sort()
result = []
heap = [(0, float('inf'))] # (neg_height, end_x)
for x, neg_h, end_x in events:
# Lazy cleanup
while heap[0][1] <= x:
heapq.heappop(heap)
if neg_h: # Start event
heapq.heappush(heap, (neg_h, end_x))
curr_max = -heap[0][0]
if not result or result[-1][1] != curr_max:
result.append([x, curr_max])
return resultdef range_add_query(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
"""Apply range updates, return final array."""
diff = [0] * (n + 1)
for start, end, val in updates:
diff[start] += val
diff[end + 1] -= val
# Convert difference array to actual values
result = []
current = 0
for i in range(n):
current += diff[i]
result.append(current)
return result| Problem Type | Start | End | Sort Key |
|---|---|---|---|
| Count overlap | (pos, +1) |
(pos, -1) |
(pos, delta) |
| Capacity | (pos, +load) |
(pos, -load) |
(pos, delta) |
| Skyline | (pos, 0, h) |
(pos, 1, h) |
(pos, type, ±h) |
| Heap skyline | (pos, -h, end) |
(pos, 0, 0) |
natural |
Document generated for NeetCode Practice Framework — API Kernel: line_sweep