Loại bỏ các khoảng được bao phủ trong C ++

Giả sử chúng ta có một danh sách các khoảng, chúng ta phải loại bỏ tất cả các khoảng bị che bởi một khoảng khác trong danh sách. Ở đây Khoảng [a, b) được bao phủ bởi khoảng [c, d) nếu và chỉ khi c <=a và b <=d. Vì vậy, sau khi làm như vậy, chúng ta phải trả lại số khoảng còn lại. Nếu đầu vào giống như [[1,4], [3,6], [2,8]], thì đầu ra sẽ là 2, Khoảng [3,6] được bao phủ bởi [1,4] và [2 , 8], vì vậy đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Sắp xếp danh sách khoảng thời gian dựa trên thời gian kết thúc
• xác định một ngăn xếp
• cho tôi trong phạm vi từ 0 đến kích thước là - 1
  • nếu ngăn xếp trống hoặc khoảng [i] và khoảng trên cùng của ngăn xếp giao nhau,
    • chèn [i] vào st
  • nếu không thì
    • tạm thời:=a [i]
    • trong khi st không trống và khoảng tạm thời và khoảng trên cùng của ngăn xếp giao nhau
      • bật ra từ ngăn xếp
    • chèn tạm thời vào st
• trả về kích thước của st.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

2