[Leetcode] 435. Non-overlapping Intervals

Identifying the Problem

interval 내에 겹치는 부분을 제거하되, 제거하는 수를 최소화하고, 제거된 interval의 수를 리턴한다.

Organizing thoughts

규칙

1. 너무 많은 범위를 잡아버리면 지울 것이 늘어난다.

2. 지우는 개수 최대 size - 1 개다.

3. interval[i][0]의 중복이 되면 안 된다.

ex : [1,2] [1,3] 이면 1이 중복이므로 하나만 남겨야 된다.

   3-1 : 하나만 남겨야 하는데 어떤 걸 남기냐면

   규칙 1을 생각했을 때, [1,3] 을 지우는 것이 옳다.

   안 겹치는 것이 중요하지, 범위를 최대화하란 말은 아니다.

 

   3-2 : 하나만 남겼을 때, 남은 하나가 다음 interval과 겹치면 이것도 지운다.

   ex : [2,6] [3,4] [4,5] [5,6]에서 [2,6]이 [3,4] [4,5] [5,6]과 곂치므로 [2,6]만 지운다.

Sourcecode

##직접 작성한 코드

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
    {
        sort(begin(intervals), end(intervals));
        
        int count = 0;
        int end = intervals[0][1];
        
        for(int i = 1; i<intervals.size(); i++)
        {
            if(intervals[i-1][0] == intervals[i][0]) //start가 같은 경우
            {count ++;  }
            else //start가 다른 경우
            {
                if(end > intervals[i][0]) //남은 하나와 겹치는 경우
                {count++; }
                else end = intervals[i][1]; //end 재설정
            }
        }
        return count;
    }
};

###정답 코드 / 출처

내 코드와의 차이점 : start가 같은 경우와 겹치는 경우를 하나로 묶어 조건을 간결하게 추렸다.

C++ | O(nlogn) | greedy - LeetCode Discuss

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int i = 1; //interval 의 index
        int c = 0; //count
        while(i<intervals.size()){
            if(intervals[i][0]<intervals[i-1][1]) //i-1과 i가 곂치면
            { 
                intervals[i][1] = min(intervals[i-1][1], intervals[i][1]); //end 재설정
                c++; //제거 카운트 증가
            }
            i++;
        }
        return c;
    }
};

Mistake

직접 작성한 코드는 다음 test에서 오류가 난다.

[[-52,31],[-73,-26],[82,97],[-65,-11],[-62,-49],[95,99],[58,95],[-31,49],[66,98],[-63,2],[30,47],[-40,-26]]

end 재설정 부분을 다시 생각해보아야겠다.