Intervals
Merging and Sorting Intervals
Written by Swapnil RajaPublished
Meeting rooms, calendar bookings, memory ranges, video segments. They are all the same problem: pairs of numbers on a line that may or may not overlap.
Sort first, almost always
Sorting by start time turns a problem about arbitrary pairs into a single left-to-right sweep. Once sorted, an interval can only overlap the one immediately before it - so a single pass is enough, and the cost is dominated by the O(n log n) sort.
Merging overlaps
javascript
function merge(intervals) {
if (intervals.length <= 1) return [...intervals]
const sorted = [...intervals].sort((a, b) => a[0] - b[0])
const merged = [sorted[0].slice()]
for (let i = 1; i < sorted.length; i++) {
const [start, end] = sorted[i]
const last = merged[merged.length - 1]
if (start <= last[1]) {
last[1] = Math.max(last[1], end) // overlaps: extend
} else {
merged.push([start, end]) // gap: start a new one
}
}
return merged
}
console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
// [[1, 6], [8, 10], [15, 18]]