Pattern Guide
Line Sweep
"Sweep a line across events. Sort by x, process events with a sorted structure."
Line sweep processes geometric or interval problems by sweeping a vertical (or horizontal) line across sorted events. At each event, update a data structure that tracks the current state. Applications: rectangle area union, sky line problem, count overlapping intervals at each point, closest pair of points, and computational geometry. The sweep converts 2D problems into 1D by processing one dimension at a time.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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;
}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 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;
}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.