C++ में रिवॉल्विंग डोर

मान लीजिए कि हमारे पास अनुरोधों की एक सूची है, जहां अनुरोध [i] में [टी, डी] शामिल है, जो समय टी पर इंगित करता है, एक व्यक्ति दरवाजे पर पहुंचा और या तो अंदर जाना चाहता था (अंदर 1 का उपयोग कर रहा है) या बाहर जाना (बाहर इंगित कर रहा है) 0 का उपयोग कर)।

इसलिए यदि केवल एक दरवाजा है और दरवाजे का उपयोग करने में एक बार की इकाई लगती है, तो कुछ नियम हैं जिनका हमें पालन करना होगा -

• दरवाजा 'इन' स्थिति से शुरू होता है और फिर अंतिम प्रतिभागी द्वारा उपयोग की जाने वाली स्थिति पर सेट हो जाता है।

• यदि दिए गए समय t पर दरवाजे पर केवल एक प्रतिभागी है, तो वे दरवाजे का उपयोग कर सकते हैं।

• यदि दो या दो से अधिक प्रतिभागी अंदर जाना चाहते हैं, तो जल्द से जल्द प्रतिभागी पहले जाता है और फिर पहले इस्तेमाल की गई दिशा को प्राथमिकता दी जाती है।

• यदि कोई एक बार की इकाई के लिए दरवाजे का उपयोग नहीं करता है, तो वह वापस प्रारंभिक अवस्था में आ जाता है।

इसलिए, हमें क्रमबद्ध सूची ढूंढनी होगी जहां प्रत्येक तत्व में [टी, डी] होता है, जो दर्शाता है कि समय टी, एक व्यक्ति या तो अंदर या बाहर गया था।

इसलिए, यदि इनपुट [[2,0], [3,1], [6,0], [6,1], [3,0]] जैसा है, तो आउटपुट [[2,0] होगा ,[3,0],[4,1],[6,1],[7,0]]

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

• सरणी को क्रमबद्ध करें v

• एक सूची बनाएं रिट

• वक्र:=1, मैं:=0, जे:=0

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

• जबकि मैं

  • यदि रिट खाली नहीं है और v[i, 0] - रिट> 1 के अंतिम तत्व का टी है, तो:

    • वर्तमान:=1

  • जे:=मैं + 1

  • आकार 2 के सरणी को परिभाषित करें

  • (गिरफ्तारी बढ़ाएं[v[i, 1]] 1 से)

  • जबकि (j

    • (गिरफ्तारी बढ़ाएं[v[j, 1]] 1 से)

  • टी:=अधिकतम (यदि रिट खाली है, तो 0, अन्यथा टी के अंतिम तत्व का टी) और v[i, 0]

  • अगर गिरफ्तारी [1] गैर-शून्य है और एआर [0] गैर-शून्य है, तो -

    • जबकि arr[curr] गैर-शून्य है, प्रत्येक चरण में arr[curr] को एक-एक करके घटाएं -

      • रिट के अंत में {t, curr} डालें

      • (टी 1 से बढ़ाएँ)

    • curr :=curr XOR 1

    • जबकि arr[curr] गैर-शून्य है, प्रत्येक चरण में arr[curr] को एक-एक करके घटाएं -

      • रिट के अंत में {t, curr} डालें

      • (टी 1 से बढ़ाएँ)

  • अन्यथा

    • वक्र:=वी[i, 1]

    • जबकि arr[curr] गैर-शून्य है, प्रत्येक चरण में arr[curr] को एक-एक करके घटाएं -

      • रिट के अंत में {t, curr} डालें

      • (टी 1 से बढ़ाएँ)

  • curr :=ret के अंतिम तत्व की दिशा

  • मैं :=जे

• वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << "[";
      for (int j = 0; j < v[i].size(); j++) {
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   vector<vector<int>> solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end());
      vector < vector <int > > ret;
      int curr = 1;
      int i = 0;
      int j = 0;
      int n = v.size();
      while(i < n){
         if(!ret.empty() && v[i][0] - ret.back()[0] > 1){
            curr = 1;
         }
         j = i + 1;
         vector <int> arr(2);
         arr[v[i][1]]++;
         while(j < n && v[j][0] == v[i][0]){
            arr[v[j][1]]++;
            j++;
         }
         int t = max((ret.empty()? 0 : ret.back()[0] + 1), v[i][0]);
         if(arr[1] && arr[0]){
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
            curr = curr ^ 1;
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }else{
            curr = v[i][1];
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }
         curr = ret.back()[1];
         i = j;
      }
      return ret;
   }
};
int main(){
   vector<vector<int>> v = {{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}};
   Solution ob;
   print_vector(ob.solve(v));
}

इनपुट

{{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}}

आउटपुट

[[2, 0, ],[3, 0, ],[4, 1, ],[6, 1, ],[7, 0, ],]