मान लीजिए हमारे पास अनुरोधों की एक सूची है, जहां requests[i] में [t, d] होता है जो दर्शाता है कि समय t पर एक व्यक्ति दरवाजे पर आया और या तो अंदर जाना चाहता था (अंदर को 1 से दर्शाया गया है) या बाहर जाना चाहता था (बाहर को 0 से दर्शाया गया है)।
यदि केवल एक दरवाजा है और इसका उपयोग करने में एक समय इकाई लगती है, तो हमें कुछ नियमों का पालन करना होगा:
- दरवाजा 'अंदर' स्थिति से शुरू होता है और फिर अंतिम प्रतिभागी द्वारा उपयोग की गई स्थिति पर सेट हो जाता है।
- यदि दिए गए समय
tपर दरवाजे पर केवल एक प्रतिभागी है, तो वे दरवाजे का उपयोग कर सकते हैं। - यदि दो या अधिक प्रतिभागी अंदर जाना चाहते हैं, तो सबसे पहले आया प्रतिभागी पहले जाता है और फिर पहले उपयोग की गई दिशा को प्राथमिकता मिलती है।
- यदि एक समय इकाई तक कोई दरवाजे का उपयोग नहीं करता है, तो यह प्रारंभिक स्थिति पर वापस आ जाता है।
हमें क्रमबद्ध सूची ज्ञात करनी है जहां प्रत्येक तत्व में [t, d] होता है, जो दर्शाता है कि समय t पर एक व्यक्ति या तो अंदर गया या बाहर गया।
उदाहरण के लिए, यदि इनपुट है [[2,0],[3,1],[6,0],[6,1],[3,0]], तो आउटपुट [[2,0],[3,0],[4,1],[6,1],[7,0]] होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- सरणी
vको सॉर्ट करें। - एक सूची
retबनाएं। curr := 1, i := 0, j := 0n := v का आकारwhile i < nकरते हुए:- यदि
retखाली नहीं है औरv[i][0] - ret के अंतिम तत्व का t > 1, तोcurr := 1 j := i + 1- आकार 2 की एक सरणी
arrपरिभाषित करें arr[v[i][1]]बढ़ाएंwhile (j < n और v[j][0], v[i][0] के समान है):arr[v[j][1]]बढ़ाएं
t := अधिकतम (यदि ret खाली है तो 0, अन्यथा ret के अंतिम तत्व का t + 1) और v[i][0]- यदि
arr[1]औरarr[0]दोनों शून्येतर हैं:while arr[curr] शून्येतर है,arr[curr]को प्रत्येक चरण में 1 से घटाएं:{t, curr}कोretके अंत में डालेंtबढ़ाएं
curr := curr XOR 1while arr[curr] शून्येतर है,arr[curr]को प्रत्येक चरण में 1 से घटाएं:{t, curr}कोretके अंत में डालेंtबढ़ाएं
- अन्यथा:
curr := v[i][1]while arr[curr] शून्येतर है,arr[curr]को प्रत्येक चरण में 1 से घटाएं:{t, curr}कोretके अंत में डालेंtबढ़ाएं
curr := ret के अंतिम तत्व की दिशाi := j
- यदि
retलौटाएं।
C++ कार्यान्वयन
#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));
return 0;
}
इनपुट
{{2, 0}, {3, 1}, {6, 0}, {6, 1}, {3, 0}}
आउटपुट
[[2, 0, ],[3, 0, ],[4, 1, ],[6, 1, ],[7, 0, ],]