[LeetCode] 435. Non-overlapping Intervals - 그리디 c++

mopevxw·2022년 1월 24일
0

LeetCode

목록 보기
9/21

그리디 풀이
1.시작시간 기준 오름차순으로 정렬
2.현재 구간 시작시간이 이전 구간 끝 시간 이상인 경우 : 현재 구간 끝 시간으로 업데이트
겹치는 경우 : ans++ / 겹치는 두 구간 중 끝나는 시간이 느린 구간 삭제 => 현재 정렬된 상태에서 끝나는 시간 느릴수록 더 많이 겹치게 된다.
ex) [1,3][2,4] [4,5]

public:
   int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       sort(intervals.begin(),intervals.end());
       int prev=-99999;
       int ans=0;
       for(auto i : intervals){
           if(i[0]>=prev) prev=i[1]; ///겹치지 않는 경우 
           else{ // 겹치는 경우
               ans++;
               prev=min(prev,i[1]); //두 구간 중 끝나는 시간 느린 구간 삭제
           }
               
       }
       return ans;
   }
};

종료시간 기준 오름차순 정렬 풀이
ex)[[2,3], [3,4], [5,6], [1,10], [6, 11], [9, 12]]
prev=min(prev,i[1]);=>종료시간 오름차순으로 필요 없어지는 코드

0개의 댓글