Non-overlapping Intervals

Problem

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

 

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

 

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

Solution

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    let overlaps = 0;
    intervals.sort((a, b) => a[1] - b[1]); // sort by end
    const stack = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const endPrev = stack[stack.length - 1][1];
        const startCur = intervals[i][0];
        if (endPrev > startCur) { // overlap
            overlaps++;
        } else { // no overlap
            stack.push(intervals[i])
        }
    }
    return overlaps;
};

We will implement a greedy solution. First, we sort intervals by the end time. Next, we iterate through all intervals. For two consecutive intervals, if the first interval's end time is greater then the second interval's start time, it must mean the two intervals overlap, and so we can discard the second interval. Repeat this process until all overlapping intervals are discarded.