C++程序：查找需要移除的最小区间数以消除重叠

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

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

• n := 数组大小
• 如果n为0，则返回0
• count := 1
• 根据区间的结束时间对数组进行排序
• end := 第一个区间的结束日期
• 对于范围1到n – 1中的i
  • 如果arr[i]的开始时间 >= end，则
    • end := arr[i]的结束时间
    • 将count加1
• 返回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

Arnab Chakraborty

更新于：2020年10月20日

413 次浏览

开启你的职业生涯

完成课程获得认证

开始学习