सी ++ में कवर किए गए अंतराल को हटा दें

मान लीजिए कि हमारे पास अंतरालों की एक सूची है, हमें सूची में किसी अन्य अंतराल द्वारा कवर किए गए सभी अंतरालों को हटाना होगा। यहां अंतराल [ए, बी) अंतराल [सी, डी) द्वारा कवर किया जाता है यदि और केवल अगर सी <=ए और बी <=डी। तो ऐसा करने के बाद, हमें शेष अंतरालों की संख्या वापस करनी होगी। यदि इनपुट [[1,4], [3,6], [2,8]] जैसा है, तो आउटपुट 2 होगा, अंतराल [3,6] [1,4] और [2] द्वारा कवर किया गया है ,8], तो आउटपुट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अंतिम समय के आधार पर अंतराल सूची को क्रमबद्ध करें
• एक स्टैक सेंट परिभाषित करें
• i के लिए 0 से लेकर a – 1 के आकार के बीच
  • यदि स्टैक खाली है या a[i] और स्टैक शीर्ष अंतराल प्रतिच्छेद कर रहा है,
    • एक [i] सेंट में डालें
  • अन्यथा
    • अस्थायी:=a[i]
    • जबकि सेंट खाली नहीं है और अस्थायी और स्टैक शीर्ष अंतराल प्रतिच्छेद कर रहा है
      • स्टैक से पॉप
    • अस्थायी को सेंट में डालें
• सेंट का रिटर्न साइज।

उदाहरण(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