C ++中的非重叠间隔

假设我们有一个间隔的集合；我们必须找到需要删除的最小间隔数，以使其余间隔不重叠。因此，如果间隔为[[1,2]，[2,3]，[3,4]，[1,3]]，则输出将为1，因为我们必须删除[1,3]才能使所有其他都不重叠。

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

• 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 = {{1,2},{1,2},{1,2}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

输入值

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

输出结果

2