C++で重複を削除するために削除する間隔の最小数を見つけるプログラム

一連の間隔があるとします。残りの間隔が重ならないようにするために削除する必要がある間隔の最小数を見つける必要があります。したがって、間隔が[[8,10]、[3,5]、[6,9]]の場合、他のすべてが重複しないように[6,9]を削除する必要があるため、出力は1になります。 。

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

• n：=配列のサイズ
• nが0の場合、0を返します
• count：=1
• 間隔の終了時間に基づいて配列を並べ替えます
• end：=最初の間隔の終了日
• 1からn–1の範囲のiの場合
  • arr [i]> =の開始時刻が終了した場合、
    • end：=到着の終了時刻[i]
    • カウントを1つ増やします
• return n – count

理解を深めるために、次の実装を見てみましょう-

例

#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 = {{8,10},{3,5},{6,9}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

入力

{{8,10},{3,5},{6,9}}

出力

1