435. Non-overlapping Intervals

문제링크: https://leetcode.com/problems/non-overlapping-intervals/

입력으로 인터벌 배열이 주어지고 겹치지 않도록하기 위해 제외해야 할 최소한의 인터벌 개수를 구하는 문제다.

Solution

Greedy

인터벌을 순서대로 넣어야 할지 판단한다면 그 기준은 인터벌의 끝값(두번째 값)을 기준으로 순서대로 넣게 된다. n-1구간까지의 인터벌을 최대로 넣었다고 가정하면 n까지의 인터벌은 구간 끝이 n으로 끝나는 인터벌을 가능한 삽입하는 것이다. 따라서 그리디로 값을 구해도 최적의 해를 구할 수 있다.

실제로 결과 배열에 삽입을 해도 되지만 결과 인터벌 배열을 리턴할 필요는 없기 때문에 제거할 인터벌만 계산한다.

Algorithm

• 인터벌의 끝 값을 기준으로 오름차순 정렬한다.
• 현재 인터벌의 끝값을 -무한대로 정의하고 순서대로 비교한다.
• 비교한 값이 삽입이 가능할 경우 끝 값을 새로 삽입한 값으로 갱신한다.
• 만약 삽입이 불가능한 값이 들어올 경우 removeCount를 증가시킨다.
• 모든 값을 탐색한 후 removeCount를 반환한다.

구현

var eraseOverlapIntervals = function(intervals) {
    // greedy
    // 일찍 끝난 순으로 정렬
    const intervals1 = intervals.sort((a, b) => a[1] - b[1]);
    
    // 앞에서 부터 겹치지 않으면 추가 후 인터벌 마지막 갱신, 겹치면 removeCounter 증가
    let curEnd = -Infinity;
    return intervals1.reduce((acc, cur) => {
        if (curEnd <= cur[0]) {
            curEnd = cur[1];
            return acc;
        } else {
            return acc + 1;
        }
    }, 0);
};