Learning Journal

2/11/2024

Non-overlapping intervals - 2nd attempt

const START = 0, END = 1;

function eraseOverlapIntervals(intervals: number[][]): number {
    if(intervals.length < 2) return 0;

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

    let first = 0, second = 1, count = 0;

    while(second < intervals.length){
        if(!intersect(intervals[first], intervals[second])){
            first = second;
        }
        else {
            count++;
        }

        second++;
    }

    return count;
}

function intersect(first:number[], second:number[]):boolean {
    return second[START] < first[END];
}const START = 0, END = 1;

function eraseOverlapIntervals(intervals: number[][]): number {
    if(intervals.length < 2) return 0;

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

    let first = 0, second = 1, count = 0;

    while(second < intervals.length){
        if(!intersect(intervals[first], intervals[second])){
            first = second;
        }
        else {
            count++;
        }

        second++;
    }

    return count;
}

function intersect(first:number[], second:number[]):boolean {
    return second[START] < first[END];
}

THE PROBLEM

I've made some improvements today with the solution. Yesterday, I sorted the array intervals by its start-point then used condition to check which one ends first to pick. Today, I sort the array by its end-point, thus, I don't need to perform the check, because the second interval will always be the one that ends at or after the first one ends. It makes the code much cleaner.

So, basically, my solution today keeps the first interval while moving the second pointer to the next interval until it finds the first interval that doesn't intersect with the first one, then, it moves the first pointer to the second pointer and move the second pointer to the next and continues the iteration.

Why does it work? Because if two intervals intersect, we need to eliminate one of them and it's better to eliminate the one that ends later so we will have space to accommodate more intervals. Because the intervals array is sorted by its end-point in ascending order, the second pointer always points to the one that ends later (and should be skipped), that's why we just need to advance the second pointer without moving the first pointer.

Revised by ChatGPT

I've made improvements to my solution today. Yesterday, I sorted the intervals array by the start points and then used a condition to determine which interval ends first for selection. Today, I refined the approach by sorting the array by the end points, thereby eliminating the need to perform the additional check. This is because the subsequent interval will always end at or after the first one, making the code much cleaner.

In essence, my current solution keeps the first interval fixed while advancing the second pointer to the next interval until it finds the first non-intersecting interval. At this point, it shifts the first pointer to the second pointer's position, moves the second pointer to the following interval, and continues this process throughout the iteration.

Why does this approach work? When two intervals intersect, it's necessary to eliminate one to make room for as many intervals as possible. It's advantageous to remove the one that ends later hence maximizing the space to accommodate more intervals. Since the intervals array is sorted by end points in ascending order, the second pointer invariably points to the interval that ends later (and should therefore be skipped), This explains why advancing the second pointer - without moving the first - is a sufficient strategy.