[NeetCode-LeetCode] Non-overlapping Intervals JAVA

반응형

728x90

[NeetCode-LeetCode] Non-overlapping Intervals - Medium

---

접근

• 그리디

---

풀이

구간이 주어지고 겹치는 구간을 제거해 총 제거된 구간이 몇 개인지 구하는 문제이다. 아래와 같은 구간이 주어질 때

intervals = [[1,2],[2,3],[3,4],[1,3]]

[1,2]와 [2,3]은 2라는 구간이 접하긴 하지만 접하는 경계면은 겹치지 않는 것으로 넘어가게 되나 [1,2]와 [2,3]을 합친 구간인 [1,3]이 뒤에 존재하기 때문에 두 구간 중 겹치는 한 구간을 제거해야 하는데 문제에서 요구하는 것은 겹치는 구간을 제거하는 최소의 비용을 원하기 때문에 [1,2], [2,3]이 제거되는 것이 아닌 [1,3]이 제거되는 것이다.

    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

우선 겹치는 구간을 제거하기 위해선 정렬을 해주고 시작해야 한다. 종료 구간을 기준으로 오름차순 정렬을 해주어야 다른 구간과 겹칠 가능성이 줄어든다. 

	int end = intervals[0][1];
        int result = 0;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                result++;
            } else {
                end = intervals[i][1];
            } 
        }

        return result;
    }

배열을 순회하며 정렬된 구간의 시작 위치가 현재 종료 위치보다 작다면 구간이 겹치는 것으로 제거를 해주어야 한다. 만약 반대로 시작 위치가 현재 종료 위치보다 크다면 겹치지 않은 새로운 구간으로 종료 위치를 갱신한다. 

---

전체 코드

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int end = intervals[0][1];
        int result = 0;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                result++;
            } else {
                end = intervals[i][1];
            } 
        }

        return result;
    }
}