Learning Journal

2/16/2024

Insert Interval

Tags: algorithms leetcode interval binary_search

function insert(intervals: number[][], newInterval: number[]): number[][] {
    
    let lo = 0, hi = intervals.length - 1;

    while(lo <= hi) {
        const mid = Math.floor((lo + hi)/2);

        if(newInterval[0] < intervals[mid][0]){
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }


    const result = intervals.slice(0, hi + 1);


    if(result.length > 0 && intersect(result[result.length - 1], newInterval)) {
        result[result.length - 1] = merge(result[result.length - 1], newInterval);

    }
    else {
        result.push(newInterval);

    }
    
    
    let curI = hi + 1;

    while(curI < intervals.length) {
        if(intersect(result[result.length - 1], intervals[curI])) {
            result[result.length - 1] = merge(result[result.length - 1], intervals[curI]);
        }
        else {
            result.push(intervals[curI]);
        }

        curI++;   
    }

    return result;


    function intersect(interval1: number[], interval2: number[]):boolean {
        return interval2[0] <= interval1[1];
    }

    function merge(interval1: number[], interval2: number[]):number[] {
        return [interval1[0], Math.max(interval1[1], interval2[1])];
    }
};function insert(intervals: number[][], newInterval: number[]): number[][] {
    
    let lo = 0, hi = intervals.length - 1;

    while(lo <= hi) {
        const mid = Math.floor((lo + hi)/2);

        if(newInterval[0] < intervals[mid][0]){
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }


    const result = intervals.slice(0, hi + 1);


    if(result.length > 0 && intersect(result[result.length - 1], newInterval)) {
        result[result.length - 1] = merge(result[result.length - 1], newInterval);

    }
    else {
        result.push(newInterval);

    }
    
    
    let curI = hi + 1;

    while(curI < intervals.length) {
        if(intersect(result[result.length - 1], intervals[curI])) {
            result[result.length - 1] = merge(result[result.length - 1], intervals[curI]);
        }
        else {
            result.push(intervals[curI]);
        }

        curI++;   
    }

    return result;


    function intersect(interval1: number[], interval2: number[]):boolean {
        return interval2[0] <= interval1[1];
    }

    function merge(interval1: number[], interval2: number[]):number[] {
        return [interval1[0], Math.max(interval1[1], interval2[1])];
    }
};

THE PROBLEM

Here is how my solution works.

First, it uses binary search to look up the index of the interval right before the new interval (which is pointed to by hi when the search stops). Then, it will add all intervals from beginning to that point to the result array. Then, it will merge the last element of the result array with the next element available of the intervals array if there is overlap. If not, it just push the interval to the result array.

Revised by ChatGPT

Here's how my solution works:

First, it utilizes binary search to find the index of the interval that comes immediately before the new interval. This index is represented by hi when the search concludes. Next, it adds all intervals from the beginning up to this point into the result array. Then, it checks if there's an overlap between the last interval in the result array and the next interval in the original intervals array. If there is an overlap, it merges these two intervals; otherwise, it simply adds the interval from the original array to the result array.