💡 풀이
var eraseOverlapIntervals = function (intervals) {
intervals.sort((a, b) => a[1] - b[1]);
let cnt = 0;
let end = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (end > intervals[i][0]) cnt++;
else end = intervals[i][1];
}
return cnt;
};📝 정리
이 문제는 대표적인 Greedy 문제라고 한다. 요즘 Greedy 관련 문제를 연습 중이었는데, 이전에 풀었던 문제와 큰 차이가 없어서 오랜 시간 동안 고민하지는 않았다.
문제는 interval이 겹치지 않게 하기 위해서 구간을 제거해야 하는데, 어떻게 하면 최소로 구간을 제거할 수 있느냐를 묻고 있다. 8개의 구간이 있다고 하고(intervals.length = 8) intervals[i][1], 즉 끝 부분(나는 코드에서는 end 변수에 담았다)을 기준으로 생각해보면,
이미지와 같이 기점으로 삼은 intervals[i][1]이 그 다음 순서의 intervals[i][0] 보다 크다면, 해당 구간은 겹치게 되는 것이다. 따라서 그 때마다 cnt++를 해주고,
만약 반대의 경우가 생긴다면 해당 순서의 intervals[i][1]을 새로운 end로 만들어주면 된다.
이렇게 반복을 하면서 겹치는 구간을 제거하면(cnt++), 마지막 loop이 끝났을 때 답을 구할 수 있다.
중요한 것은 첫 end가 가장 작은 값이 되어야 한다는 것이다. 이를 위해 intervals.sort((a, b) => a[1] - b[1]) 코드를 추가하였다.
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/non-overlapping-intervals/
