✉️문제
https://leetcode.com/problems/non-overlapping-intervals/description/
Non-overlapping Intervals - LeetCode
Can you solve this real interview question? Non-overlapping Intervals - 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.
leetcode.com
🗝 문제풀이
겹치는 부분을 최소화하는 간단한 문제이다. { start, end } 중에서 end를 기준으로 정렬하면 쉽게 풀린다.
start를 기준으로 하는 경우 다음과 같은 반례가 있다. [1, 100], [2,3][3,4]
public class NonOverlappingIntervals {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int cur = intervals[0][1];
int count = 0;
for(int i = 1; i < intervals.length; i++) {
if(intervals[i][0] >= cur) {
cur = intervals[i][1];
} else {
count++;
}
}
return count;
}
}