C++で重複しない間隔

間隔のコレクションがあるとします。残りの間隔が重ならないようにするために削除する必要のある間隔の最小数を見つける必要があります。したがって、間隔が[[1,2]、[2,3]、[3,4]、[1,3]]の場合、[1,3]を削除して作成する必要があるため、出力は1になります。他のすべては重複していません。

これを解決するには、次の手順に従います-

• n：=配列のサイズ

• nが0の場合、0を返します

• カウント：=1

• 間隔の終了時間に基づいて配列を並べ替えます

• end：=最初の間隔の終了日

• 1からn–1の範囲のiの場合

  • arr [i]> =endの開始時刻の場合、

    • 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]]

出力

2