Leet code (Medium) : 435. Non-overlapping Intervals - JAVA

 

 

이문제는 겹치는 구간을 삭제하는 문제이지만,
삭제할 구간의 "최소" 갯수를 구하는 것이 포인트다.

무심코 시작점 기준으로 오름차순 정렬 후, 시작점이 같은 경우 끝점의 오름차순으로 정렬하면 안된다..

구간의 크기가 큰 구간이 있다면, 그 뒤의 구간들 중 해당 구간의 끝점보다 끝점이 더 작거나 같은 구간들은 싹다 삭제가 될거다..
맨처음 구간만 삭제되면 될것을..

 

예를 들어,
intervals = [[1,5], [2,3], [3,4], [5,6]] 이면 
[1,5]만 삭제하면 되는데 시작점 오름차순 정렬 후, 비교하면 [2,3], [3,4]를 삭제해야 하는것으로 나온다.

 

 

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // start를 기준으로 오름차순 정렬하면 안됨.
        // 예를 들어,
        // [[1,5], [2,3], [3,4], [5,6]] 이면 
        // [1,5]만 삭제하면 되는데 오름차순 정렬로 비교하면 [2,3], [3,4]를 삭제하도록 나옴.
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int output = 0;

        int i = 1;
        int lastEnd = intervals[0][1];
        while(i < intervals.length){
            int start = intervals[i][0];
            if(lastEnd > start){
                output++;
            } else{
                lastEnd = intervals[i][1];
            }

            i++;
        }

        return output;
    }
}