C++ में दो गैर-अतिव्यापी अंतरालों का न्यूनतम आकार

मान लीजिए कि हमारे पास अंतराल की एक सूची है जहां प्रत्येक अंतराल में [प्रारंभ, समाप्ति] समय होता है। हमें किन्हीं दो गैर-अतिव्यापी अंतरालों का न्यूनतम कुल आकार ज्ञात करना है, जहाँ एक अंतराल का आकार (अंत - प्रारंभ + 1) है। अगर हमें ऐसे दो अंतराल नहीं मिलते हैं, तो 0 पर लौटें।

इसलिए, यदि इनपुट [[2,5],[9,10],[4,6]] जैसा है, तो आउटपुट 5 होगा क्योंकि हम अंतराल [4,6] चुन सकते हैं। आकार 3 और [9,10] आकार 2 का।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट :=inf

• n:=वी का आकार

• समाप्ति समय के आधार पर सरणी v को क्रमबद्ध करें

• n आकार की dp सरणी परिभाषित करें

• इनिशियलाइज़ i:=0 के लिए, जब i

  • निम्न :=0, उच्च :=i - 1

  • अस्थायी:=inf

  • वैल :=v[i, 1] - v[i, 0] + 1

  • जबकि कम <=उच्च, करें

    • मध्य:=निम्न + (उच्च-निम्न)/2

    • अगर v[मध्य, 1]>=v[i, 0], तो -

      • उच्च :=मध्य - 1

    • अन्यथा

      • अस्थायी:=न्यूनतम तापमान और डीपी [मध्य]

      • कम :=मध्य + 1

  • अगर अस्थायी inf के बराबर नहीं है, तो -

    • रिट :=न्यूनतम रिट और (अस्थायी + वैल)

    • dp[i] :=न्यूनतम वैल और टेम्परेचर

  • अन्यथा

    • डीपी [i] :=वैल

  • अगर मैं> 0, तो

    • dp[i] :=न्यूनतम dp[i] और dp[i - 1]

• वापसी (यदि रिट inf के समान है, तो 0, अन्यथा रिट)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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