Learning Journal

2/29/2024

Merge Intervals

function merge(intervals: number[][]): number[][] {
    if(intervals.length === 1) return intervals;

    intervals.sort((a, b) => a[0] - b[0]);

    let result: number[][] = [],
        curI = 0, nextI = 1;

    while(nextI < intervals.length) {
        const startVal = intervals[curI][0];
        let curEndVal = intervals[curI][1];

        while(nextI < intervals.length && curEndVal >= intervals[nextI][0]) {
            curEndVal = Math.max(curEndVal, intervals[nextI][1]);
            nextI++;
        }

        result.push([startVal, curEndVal]);
        curI = nextI;
        nextI++;
    }

    if(curI === intervals.length - 1)
        result.push(intervals[curI]);

    return result;


};function merge(intervals: number[][]): number[][] {
    if(intervals.length === 1) return intervals;

    intervals.sort((a, b) => a[0] - b[0]);

    let result: number[][] = [],
        curI = 0, nextI = 1;

    while(nextI < intervals.length) {
        const startVal = intervals[curI][0];
        let curEndVal = intervals[curI][1];

        while(nextI < intervals.length && curEndVal >= intervals[nextI][0]) {
            curEndVal = Math.max(curEndVal, intervals[nextI][1]);
            nextI++;
        }

        result.push([startVal, curEndVal]);
        curI = nextI;
        nextI++;
    }

    if(curI === intervals.length - 1)
        result.push(intervals[curI]);

    return result;


};

THE PROBLEM

My solution is to use 2 pointers, curI and nextI. First, curI points to the first element and nextI points to the second element. Then, in each iteration, I keep curI the same while advancing nextI until the interval pointed by nextI does not overlap with curI anymore. Each time nextI needs to advance 1 unit, it means the current interval that is pointed by nextI is overlap with the one pointed by curI, so, I use curEndVal to keep track of the end of that interval. When nextI stop advancing, I push the interval that start with the start value of curI interval and ends with the value pointed to by curEndVal.

The while loop stops when nextI pass the last element of intervals.

Revised by ChatGPT

My solution employs a two-pointer approach with curI and nextI. Initially, curI points to the first interval, and nextI points to the second interval. In each iteration, curI remains fixed while nextI advances until the interval at nextI no longer overlaps with the interval at curI. During this process, curEndVal is used to track the end value of the merged interval.

When nextI stops advancing, it indicates that the current interval at nextI does not overlap with the interval at curI. At this point, a merged interval is created, staring with the start value of the interval at curI and ending with the value of curEndVal. This merged interval is then added to the result array.

The loop continues until nextI has iterated through all intervals in the array. If curI is pointing to the last interval in the array, it means that this interval has not been merged with any other interval, so it is added to the result array as is.

This approach ensures that all overlapping intervals are merged efficiently.