Merge Intervals
Receives a list of [start, end] integer intervals, in any order, and returns the minimal set of non-overlapping intervals covering exactly the same points, sorted by start. It first copies and sorts the intervals by their start value — which guarantees that any interval overlapping something already emitted must overlap the most recent one — and then walks the sorted list once, keeping the last emitted range open: an interval whose start falls at or before that range's end is absorbed into it (extending its end only when it reaches further), while an interval that starts after it opens a new range. Touching intervals such as [1, 3] and [3, 5] count as overlapping. Returns the merged intervals as a new list, never mutating the caller's array; an empty input returns an empty list.
Visualization
- Input
- Result
Algorithm code
// Merge Intervals — a single pure function. Receives a list of [start, end]
// integer intervals and returns the minimal set of non-overlapping intervals
// covering exactly the same points, ordered by start. Touching intervals such
// as [1, 3] and [3, 5] count as overlapping and are merged into one.
/**
* @param {number[][]} intervals - list of [start, end] pairs, in any order
* @returns {number[][]} merged, non-overlapping intervals sorted by start
*/
export function mergeIntervals(intervals) {
if (intervals.length === 0) {
return [];
}
// Copy before sorting so the caller's array is never mutated.
const sorted = intervals.map((interval) => [...interval]).sort((a, b) => a[0] - b[0]);
const merged = [sorted[0]];
for (let i = 1; i < sorted.length; i += 1) {
const [start, end] = sorted[i];
const open = merged[merged.length - 1];
if (start <= open[1]) {
open[1] = Math.max(open[1], end);
} else {
merged.push([start, end]);
}
}
return merged;
}FUNCTION mergeIntervals(intervals):
IF length(intervals) = 0:
RETURN []
sorted ← copy of intervals ordered ascending by start
merged ← [sorted[0]]
FOR i FROM 1 TO length(sorted) - 1:
start ← sorted[i][0]
end ← sorted[i][1]
open ← merged[length(merged) - 1]
IF start ≤ open[1]:
open[1] ← max(open[1], end)
ELSE:
append [start, end] TO merged
RETURN merged