[LeetCode] No.435 Non-overlapping Intervals

문제링크

LeetCode

문제

간격의 시작시간과 종료시간이 담긴 배열이 주어질 때, 최대한 많은 간격이 안겹치도록 제거해야 할 간격수를 반환합니다.

풀이

완전탐색으로 문제를 접근하면 $O(n^2 \times 2^n)$의 시간복잡도를 가지게 되어 문제를 해결할 수 없습니다.

따라서 그리디 알고리즘으로 문제를 해결해야합니다. 종료시간을 오름차순으로 주어진 배열을 정렬하게 되면

다음 그림과 같이 정렬됩니다.

이 때, 처음 간격을 선택하고 선택한 간격에 겹칠 때, 간격을 제거해주고 겹치지 않는다면 다음 간격으로 선택해줍니다.

이 때, 제거한 간격수가 바로 최대한 많은 간격이 안겹치도록 제거한 간격수입니다.

코드

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int answer = 0;
        List<Interval> intervalsList = Arrays.stream(intervals)
            .map(arr -> new Interval(arr[0],arr[1]))
            .collect(Collectors.toList());
        Collections.sort(intervalsList);
        
        int endTime = intervalsList.get(0).getEndTime();
        for(int i = 1; i<intervalsList.size(); i++) {
            if(endTime > intervalsList.get(i).getStartTime()){
                answer++;
                continue;
            }
            endTime = intervalsList.get(i).getEndTime();
        }
        
        return  answer;
        
    }
    class Interval implements Comparable<Interval>{
        int startTime;
        int endTime;
        
        Interval(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
        
        int getStartTime(){return startTime;}
        int getEndTime(){return endTime;}
        
        @Override
        public int compareTo(Interval cmp) {
            return Integer.compare(endTime, cmp.endTime);
        }
        
        @Override
        public String toString() {
            return startTime + " to " + endTime;
        }
    }
}