Line Sweep Scanline
The line sweep algorithm processes events in sorted order, typically by position or time, maintaining an active state that updates as the sweep line moves. Commonly used for interval problems, geometric algorithms, and event-driven simulations.
1. Interval Merging Sweep Line
| Approach | Strategy | Key Steps | Complexity |
|---|---|---|---|
| Sort + Merge | Sort by start time, merge overlaps | Compare current.end with next.start | O(n log n) |
| Event-based Sweep | Create start/end events, process sorted | Track active intervals count | O(n log n) |
| Interval Tree | Augmented BST for dynamic queries | Store max endpoint in each node | O(n log n + k) |
Example: Merge Overlapping Intervals
function mergeIntervals(intervals) {
if (!intervals.length) return [];
// Sort by start time
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
const current = intervals[i];
// Check for overlap
if (current[0] <= last[1]) {
// Merge by extending the end time
last[1] = Math.max(last[1], current[1]);
} else {
// No overlap, add new interval
merged.push(current);
}
}
return merged;
}
console.log(mergeIntervals([[1,3], [2,6], [8,10], [15,18]]));
// [[1,6], [8,10], [15,18]]
console.log(mergeIntervals([[1,4], [4,5]]));
// [[1,5]]
// Variation: Merge with gap tolerance
function mergeWithGap(intervals, gap) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
const current = intervals[i];
// Merge if gap is within tolerance
if (current[0] - last[1] <= gap) {
last[1] = Math.max(last[1], current[1]);
} else {
merged.push(current);
}
}
return merged;
}
console.log(mergeWithGap([[1,2], [4,5], [7,9]], 1));
// [[1,5], [7,9]] - gap of 1 allows [1,2] and [4,5] to mergeExample: Insert Interval
function insertInterval(intervals, newInterval) {
const result = [];
let i = 0;
// Add all intervals before the new interval
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Merge overlapping intervals with new interval
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Add remaining intervals
while (i < intervals.length) {
result.push(intervals[i]);
i++;
}
return result;
}
console.log(insertInterval([[1,3], [6,9]], [2,5]));
// [[1,5], [6,9]]
console.log(insertInterval([[1,2], [3,5], [6,7], [8,10], [12,16]], [4,8]));
// [[1,2], [3,10], [12,16]]
Note: When merging intervals, always sort by start time first. Overlap exists when
current.start <= previous.end. Merged end is max(previous.end, current.end).
2. Meeting Rooms Multiple Events
| Problem Type | Approach | Key Insight | Complexity |
|---|---|---|---|
| Can Attend All | Sort and check adjacent overlaps | No overlap if sorted intervals don't touch | O(n log n) |
| Min Rooms Needed | Sweep line with start/end events | Max concurrent events = min rooms | O(n log n) |
| Free Time Intervals | Merge all busy times, find gaps | Gaps between merged intervals | O(n log n) |
Example: Meeting Rooms I - Can Attend All
function canAttendMeetings(intervals) {
if (!intervals.length) return true;
// Sort by start time
intervals.sort((a, b) => a[0] - b[0]);
// Check for any overlap
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
return false; // Overlap detected
}
}
return true;
}
console.log(canAttendMeetings([[0,30], [5,10], [15,20]])); // false
console.log(canAttendMeetings([[7,10], [2,4]])); // trueExample: Meeting Rooms II - Minimum Rooms
function minMeetingRooms(intervals) {
if (!intervals.length) return 0;
// Create separate arrays for starts and ends
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0;
let maxRooms = 0;
let startPtr = 0, endPtr = 0;
// Sweep through all events
while (startPtr < starts.length) {
if (starts[startPtr] < ends[endPtr]) {
// Meeting starts, need a room
rooms++;
maxRooms = Math.max(maxRooms, rooms);
startPtr++;
} else {
// Meeting ends, free a room
rooms--;
endPtr++;
}
}
return maxRooms;
}
console.log(minMeetingRooms([[0,30], [5,10], [15,20]])); // 2
console.log(minMeetingRooms([[7,10], [2,4]])); // 1
// Alternative: Using events with priority
function minMeetingRoomsEvents(intervals) {
const events = [];
for (const [start, end] of intervals) {
events.push([start, 1]); // Start event
events.push([end, -1]); // End event
}
// Sort by time, end events before start events at same time
events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
let rooms = 0;
let maxRooms = 0;
for (const [time, delta] of events) {
rooms += delta;
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}
console.log(minMeetingRoomsEvents([[0,30], [5,10], [15,20]])); // 2Example: Employee Free Time
// Input: list of employee schedules (each is a list of intervals)
function employeeFreeTime(schedules) {
// Flatten all intervals
const allIntervals = [];
for (const schedule of schedules) {
allIntervals.push(...schedule);
}
// Sort by start time
allIntervals.sort((a, b) => a[0] - b[0]);
// Merge all busy intervals
const merged = [allIntervals[0]];
for (let i = 1; i < allIntervals.length; i++) {
const last = merged[merged.length - 1];
const current = allIntervals[i];
if (current[0] <= last[1]) {
last[1] = Math.max(last[1], current[1]);
} else {
merged.push(current);
}
}
// Find gaps between merged intervals
const freeTime = [];
for (let i = 1; i < merged.length; i++) {
freeTime.push([merged[i - 1][1], merged[i][0]]);
}
return freeTime;
}
console.log(employeeFreeTime([
[[1,3], [6,7]],
[[2,4]],
[[2,5], [9,12]]
]));
// [[5,6], [7,9]]
// Explanation:
// Employee 1: [1,3], [6,7]
// Employee 2: [2,4]
// Employee 3: [2,5], [9,12]
// Merged busy: [1,5], [6,7], [9,12]
// Free time: [5,6], [7,9]
Note: For minimum meeting rooms, the key insight is: max concurrent meetings equals the number of rooms needed. Use two-pointer sweep with sorted start/end times or event-based approach.
3. Skyline Problem Event Points
| Component | Representation | Processing | Complexity |
|---|---|---|---|
| Critical Points | Building start/end x-coordinates | Track height changes at each x | O(n) |
| Active Heights | Multiset/heap of current building heights | Add on start, remove on end | O(log n) per event |
| Skyline Output | [x, height] when max height changes | Compare previous max with current max | O(n log n) total |
Example: Skyline Problem
function getSkyline(buildings) {
const events = [];
// Create events: [x, isStart, height]
for (const [left, right, height] of buildings) {
events.push([left, true, height]); // Start event
events.push([right, false, height]); // End event
}
// Sort events
// - By x coordinate
// - Start events before end events at same x
// - Start events: taller buildings first
// - End events: shorter buildings first
events.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
if (a[1] !== b[1]) return a[1] ? -1 : 1;
return a[1] ? b[2] - a[2] : a[2] - b[2];
});
const result = [];
const heights = new Map(); // height -> count
heights.set(0, 1); // Ground level
for (const [x, isStart, height] of events) {
if (isStart) {
heights.set(height, (heights.get(height) || 0) + 1);
} else {
const count = heights.get(height);
if (count === 1) {
heights.delete(height);
} else {
heights.set(height, count - 1);
}
}
// Get current max height
const maxHeight = Math.max(...heights.keys());
// Add to result if height changed
if (!result.length || result[result.length - 1][1] !== maxHeight) {
result.push([x, maxHeight]);
}
}
return result;
}
console.log(getSkyline([[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]));
// [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]]
// Optimized version using priority queue
class MaxHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
remove(val) {
const idx = this.heap.indexOf(val);
if (idx === -1) return;
if (idx === this.heap.length - 1) {
this.heap.pop();
return;
}
this.heap[idx] = this.heap.pop();
this.bubbleDown(idx);
}
peek() {
return this.heap[0] || 0;
}
bubbleUp(i) {
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (this.heap[p] >= this.heap[i]) break;
[this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
i = p;
}
}
bubbleDown(i) {
while (true) {
let max = i;
const left = 2 * i + 1, right = 2 * i + 2;
if (left < this.heap.length && this.heap[left] > this.heap[max]) max = left;
if (right < this.heap.length && this.heap[right] > this.heap[max]) max = right;
if (max === i) break;
[this.heap[i], this.heap[max]] = [this.heap[max], this.heap[i]];
i = max;
}
}
}
function getSkylineHeap(buildings) {
const events = [];
for (const [left, right, height] of buildings) {
events.push([left, 'start', height]);
events.push([right, 'end', height]);
}
events.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
const order = { start: 0, end: 1 };
if (a[1] !== b[1]) return order[a[1]] - order[b[1]];
return a[1] === 'start' ? b[2] - a[2] : a[2] - b[2];
});
const result = [];
const heap = new MaxHeap();
heap.push(0);
for (const [x, type, height] of events) {
const prevMax = heap.peek();
if (type === 'start') {
heap.push(height);
} else {
heap.remove(height);
}
const currMax = heap.peek();
if (currMax !== prevMax) {
result.push([x, currMax]);
}
}
return result;
}
Note: The skyline problem requires careful event sorting: start events before end events at same x, and for start events, process taller buildings first to avoid duplicate key points.
4. Rectangle Overlap Detection
| Problem Type | Approach | Key Insight | Complexity |
|---|---|---|---|
| Two Rectangles | Check boundary conditions | Overlap if NOT separated in any axis | O(1) |
| N Rectangles (Pairs) | All pairs comparison | Check each pair for overlap | O(n²) |
| Area Union (Sweep Line) | Vertical sweep with active segments | Process x-events, merge y-intervals | O(n² log n) |
| Interval Tree 2D | Separate x and y interval trees | Query overlapping intervals in both dims | O(n log n + k) |
Example: Rectangle Overlap (2 Rectangles)
// Rectangle represented as [x1, y1, x2, y2] (bottom-left, top-right)
function isRectangleOverlap(rec1, rec2) {
const [x1, y1, x2, y2] = rec1;
const [x3, y3, x4, y4] = rec2;
// Check if NOT overlapping (separated)
// Separated if: rec1 is left of rec2 OR rec1 is right of rec2
// OR rec1 is below rec2 OR rec1 is above rec2
const separated = x2 <= x3 || x4 <= x1 || y2 <= y3 || y4 <= y1;
return !separated;
}
console.log(isRectangleOverlap([0,0,2,2], [1,1,3,3])); // true
console.log(isRectangleOverlap([0,0,1,1], [1,0,2,1])); // false (touching but not overlapping)
console.log(isRectangleOverlap([0,0,1,1], [2,2,3,3])); // false
// Alternative: Check overlap directly
function isRectangleOverlapDirect(rec1, rec2) {
const [x1, y1, x2, y2] = rec1;
const [x3, y3, x4, y4] = rec2;
// Overlap in both x and y dimensions
const xOverlap = Math.max(x1, x3) < Math.min(x2, x4);
const yOverlap = Math.max(y1, y3) < Math.min(y2, y4);
return xOverlap && yOverlap;
}Example: Rectangle Area (Union of Two Rectangles)
function computeArea(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
// Calculate individual areas
const area1 = (ax2 - ax1) * (ay2 - ay1);
const area2 = (bx2 - bx1) * (by2 - by1);
// Calculate overlap area
const overlapWidth = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
const overlapHeight = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
const overlapArea = overlapWidth * overlapHeight;
// Total area = sum of areas - overlap
return area1 + area2 - overlapArea;
}
console.log(computeArea(-3, 0, 3, 4, 0, -1, 9, 2)); // 45
// Rectangle 1: 6 * 4 = 24
// Rectangle 2: 9 * 3 = 27
// Overlap: 3 * 2 = 6
// Total: 24 + 27 - 6 = 45Example: Rectangle Area II (Union of Multiple Rectangles)
function rectangleArea(rectangles) {
const MOD = 1e9 + 7;
// Collect all unique x and y coordinates
const xCoords = new Set();
const yCoords = new Set();
for (const [x1, y1, x2, y2] of rectangles) {
xCoords.add(x1);
xCoords.add(x2);
yCoords.add(y1);
yCoords.add(y2);
}
const xs = Array.from(xCoords).sort((a, b) => a - b);
const ys = Array.from(yCoords).sort((a, b) => a - b);
let totalArea = 0;
// Coordinate compression: check each grid cell
for (let i = 0; i < xs.length - 1; i++) {
for (let j = 0; j < ys.length - 1; j++) {
const x1 = xs[i], x2 = xs[i + 1];
const y1 = ys[j], y2 = ys[j + 1];
// Check if this cell is covered by any rectangle
let covered = false;
for (const [rx1, ry1, rx2, ry2] of rectangles) {
if (rx1 <= x1 && x2 <= rx2 && ry1 <= y1 && y2 <= ry2) {
covered = true;
break;
}
}
if (covered) {
const area = (x2 - x1) * (y2 - y1);
totalArea = (totalArea + area) % MOD;
}
}
}
return totalArea;
}
console.log(rectangleArea([[0,0,2,2], [1,0,2,3], [1,0,3,1]])); // 6
// Optimized sweep line approach
function rectangleAreaSweepLine(rectangles) {
const MOD = 1e9 + 7;
const events = [];
// Create events for each rectangle
for (const [x1, y1, x2, y2] of rectangles) {
events.push([x1, y1, y2, 1]); // Start of rectangle
events.push([x2, y1, y2, -1]); // End of rectangle
}
// Sort by x coordinate
events.sort((a, b) => a[0] - b[0]);
let totalArea = 0;
let prevX = 0;
const active = []; // [y1, y2, count]
for (const [x, y1, y2, type] of events) {
// Calculate area for previous x range
if (active.length > 0) {
const yLength = getTotalYLength(active);
totalArea = (totalArea + (x - prevX) * yLength) % MOD;
}
// Update active intervals
if (type === 1) {
active.push([y1, y2]);
} else {
const idx = active.findIndex(([a, b]) => a === y1 && b === y2);
active.splice(idx, 1);
}
prevX = x;
}
return totalArea;
}
function getTotalYLength(intervals) {
if (!intervals.length) return 0;
// Sort and merge intervals
const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
const merged = [sorted[0]];
for (let i = 1; i < sorted.length; i++) {
const last = merged[merged.length - 1];
const curr = sorted[i];
if (curr[0] <= last[1]) {
last[1] = Math.max(last[1], curr[1]);
} else {
merged.push(curr);
}
}
return merged.reduce((sum, [y1, y2]) => sum + (y2 - y1), 0);
}
Note: Rectangle overlap: two rectangles overlap if they are NOT separated in both x and y dimensions. For union area of multiple rectangles, use coordinate compression or sweep line with interval merging.
5. Event-driven Processing Pattern
| Pattern | Event Types | Processing Order | Use Case |
|---|---|---|---|
| Timeline Events | Start/End events with timestamps | Sort by time, process sequentially | Meeting rooms, resource allocation |
| Priority Events | Events with importance/urgency | Sort by priority, then time | Task scheduling, CPU scheduling |
| Geometric Events | Points, lines, rectangles | Sweep line in spatial order | Skyline, closest pair, intersections |
| State Transition | Events that change system state | Maintain active state, update on events | Finite state machines, simulations |
Example: Task Scheduler with Cooldown
// Given tasks and cooldown n, find minimum intervals needed
function leastInterval(tasks, n) {
// Count frequency of each task
const freq = new Map();
for (const task of tasks) {
freq.set(task, (freq.get(task) || 0) + 1);
}
// Get max frequency
const maxFreq = Math.max(...freq.values());
// Count how many tasks have max frequency
const maxCount = Array.from(freq.values()).filter(f => f === maxFreq).length;
// Calculate minimum intervals
// Pattern: A _ _ A _ _ A (for n=2, freq=3)
// Intervals = (maxFreq - 1) * (n + 1) + maxCount
const minIntervals = (maxFreq - 1) * (n + 1) + maxCount;
// Can't be less than total tasks
return Math.max(minIntervals, tasks.length);
}
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // 8
// A -> B -> idle -> A -> B -> idle -> A -> B
console.log(leastInterval(['A','A','A','B','B','B'], 0)); // 6
// A -> B -> A -> B -> A -> B
console.log(leastInterval(['A','A','A','A','A','A','B','C','D','E','F','G'], 2)); // 16
// A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> AExample: Car Fleet (Event-driven)
function carFleet(target, position, speed) {
const n = position.length;
if (n === 0) return 0;
// Create cars with their arrival times
const cars = position.map((pos, i) => ({
pos,
time: (target - pos) / speed[i]
}));
// Sort by starting position (descending - closest to target first)
cars.sort((a, b) => b.pos - a.pos);
let fleets = 0;
let slowestTime = 0;
// Process cars from closest to target
for (const car of cars) {
// If this car takes longer, it forms a new fleet
if (car.time > slowestTime) {
fleets++;
slowestTime = car.time;
}
// Otherwise, it catches up to the previous fleet
}
return fleets;
}
console.log(carFleet(12, [10,8,0,5,3], [2,4,1,1,3])); // 3
// Explanation:
// Car at position 10, speed 2: time = (12-10)/2 = 1
// Car at position 8, speed 4: time = (12-8)/4 = 1
// Car at position 5, speed 1: time = (12-5)/1 = 7
// Car at position 3, speed 3: time = (12-3)/3 = 3
// Car at position 0, speed 1: time = (12-0)/1 = 12
//
// Sorted by position: [10,8,5,3,0]
// Times: [1,1,7,3,12]
// Fleet 1: Cars at 10,8 (both arrive at time 1)
// Fleet 2: Car at 5 (arrives at time 7, catches car at 3)
// Fleet 3: Car at 0 (arrives at time 12, slowest)Example: The Earliest Moment When Everyone Becomes Friends
// Union-Find for connectivity
class UnionFind {
constructor(n) {
this.parent = Array(n).fill(0).map((_, i) => i);
this.rank = Array(n).fill(1);
this.components = n;
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return false;
// Union by rank
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
this.components--;
return true;
}
isConnected() {
return this.components === 1;
}
}
function earliestAcq(logs, n) {
// Sort logs by timestamp
logs.sort((a, b) => a[0] - b[0]);
const uf = new UnionFind(n);
// Process events in chronological order
for (const [timestamp, x, y] of logs) {
uf.union(x, y);
// Check if all are connected
if (uf.isConnected()) {
return timestamp;
}
}
return -1; // Not everyone becomes friends
}
console.log(earliestAcq([
[20190101,0,1],
[20190104,3,4],
[20190107,2,3],
[20190211,1,5],
[20190224,2,4],
[20190301,0,3],
[20190312,1,2],
[20190322,4,5]
], 6)); // 20190301
// Explanation: At timestamp 20190301, everyone becomes connected
Note: Event-driven processing follows a pattern: sort events by time/position, maintain active state, update state on each event. Use appropriate data structures (stack, heap, union-find) based on the problem requirements.
Summary: Line Sweep Scanline Pattern
- Core Concept: Process events in sorted order (time/position), maintain active state that updates at each event
- Interval Merging: Sort by start time, merge when current.start ≤ previous.end, extend end to max
- Meeting Rooms: Min rooms = max concurrent meetings, use two-pointer sweep or event-based counting
- Skyline Problem: Create start/end events, track active heights with multiset/heap, output when max changes
- Rectangle Overlap: Two rectangles overlap if NOT separated in both x and y axes
- Rectangle Area Union: Coordinate compression creates grid cells, or sweep line with y-interval merging
- Event Sorting: Critical for correctness - consider event type priority at same timestamp
- State Management: Use appropriate data structure: stack for monotonic, heap for priority, map for frequencies
- Complexity: Typically O(n log n) for sorting + O(n) or O(n log n) for processing events