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 में डालें
  • अन्यथा
    • temp := a[i]
    • जब तक st खाली नहीं है और temp और स्टैक टॉप इंटरवल इंटरसेक्ट कर रहे हैं
      • स्टैक से पॉप करें
    • temp को st में डालें
• 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