Learning Journal

3/1/2024

Merge Intervals - A faster approach

function merge(intervals: number[][]): number[][] {
    intervals.sort((a,b) => a[0] - b[0]);
    const result:number[][] = [];
    
    let start = intervals[0][0], end = intervals[0][1];

    for(let item of intervals) {
        if(end >= item[0]) {
            end = Math.max(end, item[1])
        }
        else {
            result.push([start,end]);
            start = item[0];
            end = item[1];
        }
    }

    result.push([start, end]);

    return result;
};function merge(intervals: number[][]): number[][] {
    intervals.sort((a,b) => a[0] - b[0]);
    const result:number[][] = [];
    
    let start = intervals[0][0], end = intervals[0][1];

    for(let item of intervals) {
        if(end >= item[0]) {
            end = Math.max(end, item[1])
        }
        else {
            result.push([start,end]);
            start = item[0];
            end = item[1];
        }
    }

    result.push([start, end]);

    return result;
};

THE PROBLEM

I copied this approach from the fastest solution on Leetcode. It is much faster than my solution. Let me try to break it down to see why.

This approach goes over all intervals, one by one, starting from the first interval. At first, it set start and end to be the start and end values of the first interval, respectively.

At each iteration, there are only two scenarios. First, the current item overlaps with the previous item. Second, the current item does not overlap with the previous item.

If it is the first scenario, it sets the end to be the maximum value between the end of the current item or current value of end (which is the end of the previous item). Basically, after the iteration, end holds the value of the current valid interval that will be pushed onto the result.
If it is the second scenario, it means now start and end holds the value of the current valid interval that should be pushed onto the result. So, the pushing happens. Then, start and end will be set to the start and end values of the current item.

Revised by ChatGPT

I adapted this solution from the fastest submission on LeetCode. It outperforms my initial solution in terms of speed. Here's a breakdown of how it works:

The algorithm sorts the intervals based on their start values. It then initializes start and end variables with the start and end values of the first interval, respectively.

It iterates over each interval in the sorted list, handling two scenarios at each step:

Overlap: If the current interval overlaps with the ongoing interval (i.e., end >= item[0]), the algorithm updates end to be the maximum of the current end and the end value of the current internal. This effectively extends the ongoing interval to include the current interval.
No Overlap: If the current interval does not overlap with the ongoing interval, the algorithm adds the ongoing interval ([start,end]) to the result list. It then updates start and end to be the start and end values of the current interval, starting a new interval.

After iterating through all intervals, the algorithm adds the last ongoing interval to the result list.

This approach efficiently merges overlapping intervals by continuously updating the end of the ongoing interval and adding it to the result list only when a non-overlapping interval is encountered.