Intervals: merge & insert

O(n log n)

Sort intervals by start, then walk once: if the next interval starts before (or at) the current one's end, fold it in by extending the end; otherwise close the current interval and open a new one.

Signals

merge overlapping intervalsinsert a new interval into a sorted listmeetings, bookings, or ranges that overlapgiven as [start, end] pairsfree time / busy time between intervals

Template

function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const result = [];
    for (const [start, end] of intervals) {
        const last = result[result.length - 1];
        if (last && start <= last[1]) {
            last[1] = Math.max(last[1], end);
        } else {
            result.push([start, end]);
        }
    }
    return result;
}

Looks similar, isn't

Sweep line: Merging coalesces overlapping ranges into fewer, wider ranges as the final answer. A sweep line instead turns each interval into +1/-1 events to count how many are active at any moment, a different question (busiest point, not combined ranges).

n up to 1e5 intervals -> O(n log n): the sort dominates; the merge pass itself is a single O(n) scan.

Learn this pattern