[75 LeetCode] 31 - Non-overlapping Intervals

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

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

Non-overlapping Intervals - LeetCode

 

대표적인 greedy 문제인데, 생각해내지 못해서 틀렸다.

greedy임을 알 때 구현난이도는 굉장히 낮다.

end 순으로 정렬 후 순회하며 겹치지 않는 경우에 결과 배열에 넣어주면 된다.

var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    const res = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {      
        if (res[res.length - 1][1] > intervals[i][0]) continue;

        res.push(intervals[i]);
    }
    return intervals.length - res.length;

};