Non-overlapping Intervals

(start, end)로 이루어진 구간 배열에서 서로 겹치지 않는 구간들만 남기기 위하여 지워야 하는 최소 원소의 개수를 구하는 문제이다. 구간의 겹침은 2번 구간의 시작 점이 1번 구간의 끝 지점 앞에 있다면 겹친다고 할 수 있다. 그리고 두 구간이 겹친다면 범위가 더 좁을 수록 좋다고 할 수 있다

.

구간을 효율적으로 비교하기 위하여 시작 지점을 기반으로 정렬한 이후 현재 위치보다 뒤에 있는 배열을 비교하며 체크해 주었다. 아래는 통과한 코드이다.

import java.util.*;  
  
class Solution {  
    public int eraseOverlapIntervals(int[][] intervals) {  
        Arrays.sort(intervals, (a, b) -> {  
            return Integer.compare(a[0],b[0]);  
        });  
  
        int answer = 0;  
        boolean[] removed = new boolean[intervals.length];  
        for(int i = 0; i < intervals.length - 1; i++){  
            if(removed[i]) continue;  
  
            int[] itv1 = intervals[i];  
            for(int j = i + 1; j < intervals.length; j++){  
                if(removed[j]) continue;  
  
                int[] itv2 = intervals[j];  
                if(itv2[0] < itv1[1]){  
                    answer++;  
                    if(itv1[1] > itv2[1]){  
                        removed[i] = true;  
                        break;  
                    }  
                    removed[j] = true;  
                }  
            }  
        }  
  
        return answer;  
    }  
}

 

하지만 이보다 더 효율적인 속도가 나오는 코드들이 있어 확인했다. 내가 해결한 코드의 경우 제거한 이후에는 removed 배열을 만들어 체크해주며 중복 체크를 피하고 있었다.

 

하지만 더 효율적인 속도의 코드의 경우 한번의 for문으로 해결하고 있었다. 각 요소를 한번만 체크하고 바로 제거할 것을 확인한 이후 다음 요소로 건너가는 방법이었다. 이 때 비교 군은 변수에 저장하여 유지하는 방식이었다. 그 방법은 아래와 같다.

 

```java
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        
        Arrays.sort(intervals , (a,b) -> a[0]-b[0]);
        int s1 = intervals[0][0];
        int e1 = intervals[0][1];
        int cnt = 0;

        for(int i=1;i<intervals.length;i++){

            int s2 = intervals[i][0];
            int e2 = intervals[i][1];

            if(e1 > s2){
                cnt++;
                s1 = s1;
                e1 = Math.min(e1,e2);
                continue;
            }

            s1 = s2;
            e1 = e2;
        }
        return cnt;
    }
}