Pattern Reference
Line Sweep
"Sweep-line algorithm for interval union, skyline, rectangle area, closest pair."
Loading...
Deep Dive Tutorial
Line sweep: sort all "events" (interval starts, ends, points) by their x-coordinate. Sweep left to right, maintaining an active set. When an interval starts, add to active set. When it ends, remove. Between events, compute what's needed (count active intervals, find gaps, merge ranges). The key: what data structure does the active set need? Often a sorted multiset or segment tree.
Line sweep template — interval coverage
// Line sweep for interval coverage / overlap counting
function sweepIntervals(intervals) {
const events = [];
for (const [l, r] of intervals) {
events.push([l, 1]); // start event
events.push([r, -1]); // end event
}
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // sort by x, ends before starts at same x
let active = 0, maxOverlap = 0;
for (const [x, type] of events) {
active += type;
maxOverlap = Math.max(maxOverlap, active);
}
return maxOverlap;
}
// For computing total covered length:
function coveredLength(intervals) {
// Sort by start, merge overlapping
intervals.sort((a, b) => a[0] - b[0]);
let total = 0, curEnd = -Infinity;
for (const [l, r] of intervals) {
if (l > curEnd) { total += r - l; curEnd = r; }
else if (r > curEnd) { total += r - curEnd; curEnd = r; }
}
return total;
}Worked Problems
ruler
Line sweep pattern:
1. Convert problem into events (start/end of intervals or objects)
2. Sort events by position (x or time)
3. Process events left to right, maintaining an active set
4. Query/update active set at each event
Active set choices:
- Count of active intervals: simple counter
- Max active value: max-heap
- Covered length on 1D axis: segment tree with lazy count
- Set of active segments: balanced BST (sorted set)
Sorting trick: When start and end events occur at same x, process ENDS before STARTS (for non-overlapping intervals) or STARTS before ENDS (for strict overlap counting) — depends on problem definition.
1. Convert problem into events (start/end of intervals or objects)
2. Sort events by position (x or time)
3. Process events left to right, maintaining an active set
4. Query/update active set at each event
Active set choices:
- Count of active intervals: simple counter
- Max active value: max-heap
- Covered length on 1D axis: segment tree with lazy count
- Set of active segments: balanced BST (sorted set)
Sorting trick: When start and end events occur at same x, process ENDS before STARTS (for non-overlapping intervals) or STARTS before ENDS (for strict overlap counting) — depends on problem definition.