Merge Intervals

Problem Summary

Given an array of intervals where each intervals[i] = [start, end] represents a time interval, merge all overlapping intervals into a single merged interval and return an array of non-overlapping intervals that cover the entire range of the input intervals.

Two intervals overlap if they share any common point. For example, [1,3] and [2,6] overlap because they both cover the range [2,3], while [1,3] and [3,4] also overlap at the boundary point 3.

Visual Example:

Before merging:
[1-----3]  
        [2--------6]
              [8--10]
                       [15--18]

After merging:
[1-----------6]
              [8--10]
                       [15--18]

Constraints:

Array contains between 1 and 10,000 intervals
Each interval has exactly 2 elements: [start, end]
Start and end values are non-negative integers up to 10,000, where start <= end

Techniques

Array
Sorting

Solution

function merge(intervals: number[][]): number[][] {
    intervals.sort((a, b) => a[0] - b[0])

    const result: number[][] = []

    for (const interval of intervals) {
        const last = result[result.length - 1]

        if (last && interval[0] <= last[1]) {
            last[1] = Math.max(last[1], interval[1])
        } else {
            result.push(interval)
        }
    }

    return result
};