(Leetcode) 435 - Non-overlapping Intervals 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/non-overlapping-intervals/description/
내가 작성한 풀이
먼저 입력으로 들어온 intervals를 정렬 한다. interval 간에 overlapping이 발생된 경우 end 값이 짧은 쪽을 택한다. 그래야 추후에 더 많은 interval을 선택할 수 있다.
public int eraseOverlapIntervals(int[][] intervals) {
int overlappingCount = 0;
Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
for (int i = 0; i < intervals.length - 1; i++) {
// overlapping 이 발생된 경우
if (intervals[i][1] > intervals[i + 1][0]) {
overlappingCount++;
// 앞 interval 의 end 값이 뒤 interval 의 end 보다 작을 경우 swap
if (intervals[i][1] < intervals[i + 1][1]) {
int[] temp = intervals[i];
intervals[i] = intervals[i + 1];
intervals[i + 1] = temp;
}
}
}
return overlappingCount;
}
TC, SC
시간 복잡도는 O(n*logn) 공간 복잡도는 O(1) 이다.
swap 없이 pointer를 사용하여 풀기
첫번째 풀이는 swap이 필요하다. pointer를 통해서 개선할 수 있을 것으로 보여서 개선해보았다.
public int eraseOverlapIntervals(int[][] intervals) {
int overlappingCount = 0;
Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
int currentEnd = intervals[0][1];
for (int i = 0; i < intervals.length - 1; i++) {
// overlapping 이 발생된 경우
if (currentEnd > intervals[i + 1][0]) {
overlappingCount++;
// 앞 interval 의 end 값이 뒤 interval 의 end 보다 작을 경우 이전 pointer 유지
if (currentEnd < intervals[i + 1][1]) {
continue;
}
}
currentEnd = intervals[i + 1][1];
}
return overlappingCount;
}
TC, SC
시간 복잡도는 O(n*logn) 공간 복잡도는 O(1) 이다.