C++ এ অ-ওভারল্যাপিং ব্যবধান

ধরুন আমাদের কাছে ব্যবধানের একটি সংগ্রহ আছে; বাকি ব্যবধানগুলিকে নন-ওভারল্যাপিং করতে আমাদের ন্যূনতম সংখ্যক ব্যবধান বের করতে হবে। সুতরাং যদি ব্যবধান [[1,2], [2,3], [3,4], [1,3]] হয়, তাহলে আউটপুট হবে 1, যেমনটি তৈরি করতে আমাদের [1,3] অপসারণ করতে হবে। অন্য সবগুলো অ-ওভারল্যাপিং।

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

• n :=অ্যারের আকার

• যদি n 0 হয়, তাহলে 0 ফেরত দিন

• গণনা :=1

• ব্যবধানের শেষ সময়ের উপর ভিত্তি করে অ্যারে সাজান

• শেষ :=প্রথম ব্যবধানের শেষ তারিখ

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • যদি arr[i]>=শেষের শুরুর সময়, তারপর

    • শেষ :=আরার[i]

      শেষ সময়

    • গণনা 1 দ্বারা বৃদ্ধি করুন

• ফেরত n – গণনা

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   int eraseOverlapIntervals(vector<vector<int>>& arr) {
      int n = arr.size();
      if(!n)return 0;
      int cnt = 1;
      sort(arr.begin(), arr.end(), cmp);
      int end = arr[0][1];
      for(int i = 1; i < n; i++){
         if(arr[i][0] >= end){
            end = arr[i][1];
            cnt++;
         }
      }
      return n - cnt;
   }
};
main(){
   vector<vector<int>> v = {{1,2},{1,2},{1,2}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

ইনপুট

[[1,2],[1,2],[1,2]]

আউটপুট

2