[PS] Leet | 435. 겹치지 않는 구간들

문제

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

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are 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.

조건

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

답

Greedy로 해결할 수 있습니다.

 

최소한의 구간을 제거하여 겹친 부분이 없게 만들어야 한다는 조건을 구간의 개수를 최대한 많이 남기면서 겹친 부분이 없게 만들어야 한다는 조건으로 해석할 수 있습니다.

 

intervals를 end_i의 오름차순으로 정렬한 후 겹치는 부분이 생기는 구간들만 제거한다면, 위와 같은 조건을 만족시킬 수 있습니다.

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    const len = intervals.length;
    let minNum = 0;
    let index = 0;

    if (len === 0) return 0;

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

    for (let i=1; i<len; ++i) {
        if (intervals[i][0] < intervals[index][1]){
            minNum++;
        } else {
            index = i;
        }
    }

    return minNum;
};

시간 복잡도 : O(nlogn)

공간 복잡도 : O(1)