Array : Non-overlapping Intervals

https://leetcode.com/problems/non-overlapping-intervals/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

안겹치는 인터벌들을 최대한 많이 남겨둘려면 몇개의 인터벌을 지워야 하는가? 라는 문제다.

그니까 안겹치는 인터벌들을 최대한 많이 남겨두는 문제랑 똑같고 이는 Interval Scheduling이라는 웰노운 알고리즘이라고 한다.

 

그리디 해법 설명이 잘 된 블로그 링크 : https://velog.io/@claude_ssim/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Greedy-Algorithm-Interval-Scheduling

velog

 

이 증명이 제일 인상깊었다.

해법은 end를 기준으로 정렬해서 겹치지 않는 애들만 추가하는 방식인데,

이게 만약 옵티멀이 아니라면 r까진 옵티멀 솔루션이랑 같다고 가정했을때

r + 1도 greedy 알고리즘의 인터벌이 먼저끝나므로 OPT r+1을  GREEDY r+1로 대체해도 옵티멀이 돼서 모순이라는 것이다.

 

저 블로그도 외국자료를 번역만 해주신거같고 원본은  https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms-2x2.pdf

 

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[1])
        count = 0
        prevEnd = -50000

        for interval in intervals:
            if prevEnd <= interval[0]:
                count += 1
                prevEnd = interval[1]
        
        return len(intervals) - count

안겹치는 인터벌을 최대한 많이 찾아서 전체 개수에서 빼주면 몇개를 지워야되는지 알수있다.

직관적으로 보면 가장 빨리 끝나는 인터벌을 스케줄링해야 남는 시간이 많아지니까 더 많은 인터벌을 스케줄할수있다는..?

 

이 문제는 DP로도 풀수있는데

/*
https://leetcode.com/problems/non-overlapping-intervals/solutions/1358165/java-simple-dp-solution/
1. Sort the interval based on start and end time
2. For each interval, do the following
	3. If interval is not overlapping, move on to next interval
	4. Else, we heve two choices make and find the minimum intervals to remove.
		5. Ignore the current one (or)
		6. Remove as many intervals in left untill it is not overlapping.
3. Return the result
*/
public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a,b) -> a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
    int n = intervals.length;
    int[] dp = new int[n];
    for(int i=1;i<n;i++) {
        if(intervals[i-1][1]<=intervals[i][0]) {
            dp[i] = dp[i-1];
        } else {
            int count = 0, j=i-1;
            while(j>=0 && intervals[j][1]>intervals[i][0]) {
                count++;
                j--;
            }
            if(j>=0) {
                count += dp[j];
            }
            dp[i] = Math.min(1+ dp[i-1], count);
        }
    }
    return dp[n-1];
}

이 알고리즘을 해석하자면

i에서 i-1인터벌이랑 안겹치면 dp[i] = dp[i-1]

만약 겹치게 되면 두 케이스로 나눠서 미니멀을 찾는다.

1. 인터벌 i를 남겨두기 위해 몇 개를 지워야되는지 계산

2. 인터벌 i를 지워버리기

 

인터벌 i를 지워버리는게 Math.min함수의 첫번째 인자로 들어간 1 + dp[i-1]이고

그 위쪽 코드는 인터벌 i를 남겨두기 위해 몇 개를 지워야되는지 계산하는 부분이다.

 

어렵네

 

----수정----

위  dp 솔루션은 while문 때문에 O(N^2)이 되어서 TLE가 발생한다.

두 가지 해결 방법이 있다.

(1) while문 대신 binary search로 찾기

(2) 다른 DP 방법 이용

 

 

다른 DP 방법

class Solution:
    def eraseOverlapIntervals(self, intervals: 'List[Interval]') -> 'int':
        if not intervals:
            return 0
        
        '''
        dp[j] = minimum amount amount of intervals you need to remove in order
        to intervals nonoverlaping, up to index j
        
        if it is overlapping, it must be removed, and  dp[j] = 1+dp[j-1] if curr.first <= bound (which is initailized to intrevals[0].end --- we sort with start interval as priority). 
        but we don't know removing which one will make it minimum, so take the new bound as minimum(bound, curr.end)
        this works in a greedy way because if we take the minimum ending interval, it's the best chance that something else won't overlap
        if it must not be removed, then dp[j] = dp[j-1]  and we update the new bound
        
        '''
        intervals = sorted(intervals, key = lambda x: x.start) 
        dp = [0]*len(intervals)
        bound = intervals[0].end
        for i in range(1, len(intervals)):
            if intervals[i].start < bound:
                bound = min(bound, intervals[i].end)
                dp[i] = dp[i-1]+1
            else:
                bound = intervals[i].end
                dp[i] = dp[i-1]
        return dp[-1]