C++ এ আচ্ছাদিত ব্যবধান সরান

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• শেষ সময়ের উপর ভিত্তি করে ব্যবধান তালিকা সাজান
• একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
• আমি 0 থেকে a – 1
  এর পরিসরে
  • যদি স্ট্যাক খালি হয় বা a[i] এবং স্ট্যাকের উপরের ব্যবধান ছেদ করা হয়,
    • st-এ a[i] ঢোকান
  • অন্যথায়
    • temp :=a[i]
    • যখন st খালি নয় এবং temp এবং stack top interval ছেদ করছে
      • স্ট্যাক থেকে পপ
    • st-এ temp সন্নিবেশ করুন
• স্টের রিটার্ন সাইজ।

উদাহরণ(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