ลบช่วงเวลาที่ครอบคลุมใน C ++

สมมติว่าเรามีรายการช่วงเวลา เราต้องลบช่วงเวลาทั้งหมดที่ครอบคลุมโดยช่วงเวลาอื่นในรายการ ที่นี่ ช่วง [a,b) ครอบคลุมโดยช่วง [c,d) ถ้าหาก c <=a และ b <=d เท่านั้น ดังนั้นหลังจากทำเช่นนั้น เราต้องคืนค่าจำนวนช่วงที่เหลือ หากอินพุตเป็นเหมือน [[1,4],[3,6],[2,8]] เอาต์พุตจะเป็น 2 ช่วง [3,6] จะถูกครอบคลุมโดย [1,4] และ [2 ,8] ดังนั้นผลลัพธ์จะเป็น 2.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จัดเรียงรายการช่วงเวลาตามเวลาสิ้นสุด
• กำหนดสแต็ก st
• สำหรับ i ในช่วง 0 ถึงขนาด a – 1
  • ถ้าสแต็กว่างเปล่าหรือ a[i] และช่วงบนสุดของสแต็กกำลังตัดกัน
    • แทรก a[i] ลงใน st
  • อย่างอื่น
    • อุณหภูมิ :=a[i]
    • ในขณะที่ st ไม่ว่างเปล่า และ temp และ stack top ช่วงกำลังตัดกัน
      • ป๊อปจากสแต็ก
    • ใส่ temp ลงใน 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