C ++中移除被覆盖的间隔

假设我们有一个间隔列表，我们必须删除列表中另一个间隔覆盖的所有间隔。在且仅当c <= a和b <= d时，间隔[a，b）才由间隔[c，d）覆盖。因此，这样做之后，我们必须返回剩余间隔的数量。如果输入类似于[[1,4]，[3,6]，[2,8]]，则输出为2，间隔[3,6]由[1,4]和[2覆盖，8]，因此输出为2。

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

• 根据结束时间对间隔列表进行排序

• 定义一个堆栈st

• 当我的范围是0到a – 1的大小时

• temp：= a [i]

• 当st不为空且temp和stack top间隔相交时

• 将temp插入st

• 从堆栈弹出

• 将a [i]插入st

• 如果堆栈为空或a [i]并且堆栈顶部间隔相交，

• 除此以外

• st的返回大小。

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool intersect(vector <int>& a, vector <int>& b){
      return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
   }
   static bool cmp(vector <int> a, vector <int> b){
      return a[1] < b[1];
   }
   void printVector(vector < vector <int> > a){
      for(int i = 0; i < a.size(); i++){
         cout << a[i][0] << " " << a[i][1] << endl;
      }
      cout << endl;
   }
   int removeCoveredIntervals(vector<vector<int>>& a) {
      sort(a.begin(), a.end(), cmp);
      stack < vector <int> > st;
      for(int i = 0; i < a.size(); i++){
         if(st.empty() || !intersect(a[i], st.top())){
            st.push(a[i]);
         }
         else{
            vector <int> temp = a[i];
            while(!st.empty() && intersect(temp, st.top())){
               st.pop();
            }
            st.push(temp);
         }
      }
      return st.size();
   }
};
main(){
   vector<vector<int>> v = {{1,4},{3,6},{2,8}};
   Solution ob;
   cout << (ob.removeCoveredIntervals(v));
}

输入项

[[1,4],[3,6],[2,8]]

输出结果

2