程序查找要删除的最小间隔数，以消除C ++中的重叠

假设我们有一组间隔；我们必须找到应删除的最小间隔数，以使其余间隔不重叠。因此，如果间隔为[[8,10]，[3,5]，[6,9]]，则输出将为1，因为我们必须删除[6,9]以使所有其他区域不重叠。

为了解决这个问题，我们将遵循以下步骤-

• n：=数组大小

• 如果n为0，则返回0

• 数：= 1

• 根据间隔的结束时间对数组排序

• 结束：=第一个间隔的结束日期

• 当我在1到n – 1的范围内时

• end：= arr [i]的结束时间

• 计数增加1

• 如果arr [i]的开始时间> =结束，则

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

输入值

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

输出结果

1