박종훈 알고리즘 블로그

(Leetcode) 435 - Non-overlapping Intervals 풀이

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice


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) 이다.