C++의 겹치지 않는 간격

<시간/>

간격 모음이 있다고 가정합니다. 나머지 구간이 겹치지 않게 하기 위해 제거해야 하는 최소 구간 수를 찾아야 합니다. 따라서 간격이 [[1,2], [2,3], [3,4], [1,3]]이면 출력은 1이 됩니다. 나머지는 모두 겹치지 않습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기
n이 0이면 0을 반환합니다.
개수 :=1
간격의 종료 시간을 기준으로 배열 정렬
end :=첫 번째 간격의 종료 날짜
범위 1에서 n – 1까지의 i에 대해
- arr[i]의 시작 시간>=끝이면
  - end :=arr[i]의 종료 시간
  - 1만큼 카운트 증가
리턴 n – 카운트

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   int eraseOverlapIntervals(vector<vector<int>>& arr) {
      int n = arr.size();
      if(!n)return 0;
      int cnt = 1;
      sort(arr.begin(), arr.end(), cmp);
      int end = arr[0][1];
      for(int i = 1; i < n; i++){
         if(arr[i][0] >= end){
            end = arr[i][1];
            cnt++;
         }
      }
      return n - cnt;
   }
};
main(){
   vector<vector<int>> v = {{1,2},{1,2},{1,2}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

입력

[[1,2],[1,2],[1,2]]