Merge Intervals medium

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This is crucial for efficiently detecting overlaps.

2. Initialize the merged intervals array: Create an empty array to store the merged intervals.

3. Iterate through the sorted intervals:

   • If the current interval's start time is less than or equal to the last merged interval's end time, it means there's an overlap. Merge the intervals by updating the last merged interval's end time to the maximum of its current end time and the current interval's end time.
   • If there's no overlap, the current interval is added as a new merged interval to the result array.

4. Return the merged intervals: The final array contains all the non-overlapping merged intervals.

Explanation

The key idea is sorting the intervals. Once sorted, we can iterate through them and efficiently determine overlaps by comparing the start time of the current interval with the end time of the previously merged interval. If they overlap, we merge them by extending the end time of the merged interval; otherwise, we add the current interval as a new merged interval.

Code

function merge(intervals: number[][]): number[][] {
    // 1. Sort intervals by start time
    intervals.sort((a, b) => a[0] - b[0]);

    const merged: number[][] = [];
    let lastMergedInterval: number[] | null = null;

    // 2. Iterate and merge
    for (const interval of intervals) {
        if (lastMergedInterval === null) {
            // First interval
            lastMergedInterval = interval;
        } else {
            //Check for overlap
            if (interval[0] <= lastMergedInterval[1]) {
                // Overlap: Merge
                lastMergedInterval[1] = Math.max(lastMergedInterval[1], interval[1]);
            } else {
                // No overlap: Add previous merged interval to result and start a new one
                merged.push(lastMergedInterval);
                lastMergedInterval = interval;
            }
        }
    }

    //Add the last merged interval to the result
    if(lastMergedInterval){
        merged.push(lastMergedInterval);
    }

    return merged;
}

Complexity

• Time Complexity: O(n log n), dominated by the sorting step.
• Space Complexity: O(n) in the worst case (if no intervals merge), to store the merged array. In best case it could be O(1) if all intervals merge into a single interval.