C++-এ কভার্ড ইন্টারভাল সরানো

মনে করুন একটি ইন্টারভাল লিস্ট আছে, আমাদের লিস্টে অন্য কোনো ইন্টারভাল দ্বারা কভার করা সব ইন্টারভাল সরাতে হবে। এখানে ইন্টারভাল [a,b) কভার করা হয় ইন্টারভাল [c,d) দ্বারা যদি এবং কেবল যদি `c <= a` এবং `b <= d`। এটি করার পর, অবশিষ্ট ইন্টারভালের সংখ্যা রিটার্ন করতে হবে। যদি ইনপুট হয় `[[1,4],[3,6],[2,8]]`, তবে আউটপুট হবে ২, ইন্টারভাল [3,6] [1,4] এবং [2,8] দ্বারা কভার করা হয়েছে, তাই আউটপুট ২।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

ইন্টারভাল লিস্টকে এন্ডিং টাইম অনুযায়ী সোর্ট করুন
একটি স্ট্যাক `st` সংজ্ঞায়িত করুন
`i` = 0 থেকে `a`-এর আকার - 1 পর্যন্ত
- যদি স্ট্যাক খালি থাকে অথবা `a[i]` এবং স্ট্যাক টপ ইন্টারভাল ইন্টারসেক্ট করে, তবে
  - `a[i]`-কে `st`-এ ইনসার্ট করুন
- অন্যথায়
  - `temp := a[i]`
  - যখন `st` খালি না থাকে এবং `temp` এবং স্ট্যাক টপ ইন্টারভাল ইন্টারসেক্ট করে
    - স্ট্যাক থেকে পপ করুন
  - `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]]