C++ এ দুটি নন-ওভারল্যাপিং ব্যবধানের ন্যূনতম আকার

ধরুন আমাদের কাছে একটি ব্যবধানের তালিকা রয়েছে যেখানে প্রতিটি ব্যবধানে [শুরু, শেষ] বার রয়েছে। আমাদের যেকোন দুটি অ-ওভারল্যাপিং ব্যবধানের সর্বনিম্ন মোট আকার খুঁজে বের করতে হবে, যেখানে একটি ব্যবধানের আকার (শেষ - শুরু + 1)। যদি আমরা এই ধরনের দুটি ব্যবধান খুঁজে না পাই, 0 ফেরত দিন।

সুতরাং, যদি ইনপুটটি [[2,5],[9,10],[4,6]] এর মত হয়, তাহলে আউটপুট হবে 5 কারণ আমরা ব্যবধান বেছে নিতে পারি [4,6] সাইজ 3 এবং [9,10] সাইজ 2 এর।

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

• ret :=inf

• n :=v

  এর আকার

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

• n

  আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • নিম্ন :=0, উচ্চ :=i - 1

  • temp :=inf

  • val :=v[i, 1] - v[i, 0] + 1

  • যখন কম <=উচ্চ, করুন

    • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2

    • যদি v[মিড, 1]>=v[i, 0], তাহলে −

      • উচ্চ :=মধ্য - 1

    • অন্যথায়

      • temp :=সর্বনিম্ন তাপমাত্রা এবং dp[মধ্য]

      • নিম্ন :=মধ্য + 1

  • যদি temp inf এর সমান না হয়, তাহলে −

    • ret :=ret এর সর্বনিম্ন এবং (temp + val)

    • dp[i] :=ন্যূনতম ভ্যাল এবং টেম্প

  • অন্যথায়

    • dp[i] :=val

  • যদি আমি> 0, তাহলে

    • dp[i] :=ন্যূনতম dp[i] এবং dp[i - 1]

• রিটার্ন (যদি ret একই হয় inf, তাহলে 0, অন্যথায় ret)

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

উদাহরণ

#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 solve(vector<vector<int>>& v) {
      int ret = INT_MAX;
      int n = v.size();
      sort(v.begin(), v.end(), cmp);
      vector <int> dp(n);
      for(int i = 0; i < v.size(); i++){
         int low = 0;
         int high = i - 1;
         int temp = INT_MAX;
         int val = v[i][1] - v[i][0] + 1;
         while(low <= high){
            int mid = low + (high - low) / 2;
            if(v[mid][1] >= v[i][0]){
               high = mid - 1;
            }else{
               temp = min(temp, dp[mid]);
               low = mid + 1;
            }
         }
         if(temp != INT_MAX){
            ret = min(ret, temp + val);
            dp[i] = min(val, temp);
         }else{
            dp[i] = val;
         }
            if(i > 0) dp[i] = min(dp[i], dp[i - 1]);
      }
      return ret == INT_MAX ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{2,5},{9,10},{4,6}};
   cout << (ob.solve(v));
}

ইনপুট

{{2,5},{9,10},{4,6}}

আউটপুট

5