समस्या
एक बैंक में tellers कैशियर हैं और इंतज़ार के लिए एक ही कतार है। ग्राहक i मिनट arrivals[i] पर आता है और उसे कैशियर के पास service[i] मिनट लगते हैं। ग्राहकों को सख़्ती से आने के क्रम में (lists के क्रम में) सेवा मिलती है। जब कोई ग्राहक कतार में सबसे आगे पहुँचता है, तो वह उस कैशियर के पास जाता है जो सबसे पहले ख़ाली होता है (बराबरी होने पर सबसे छोटे नंबर वाला), और अपने आने के समय और उस कैशियर के ख़ाली होने के समय में से जो बाद में हो, उस पर शुरू करता है। हर कैशियर मिनट 0 से ख़ाली है।
ग्राहक का इंतज़ार है उसका शुरू होने का समय घटा आने का समय।
bank_queue_simulation(arrivals, service, tellers) लिखिए।
इनपुट
arrivals: आने के मिनट, घटते नहीं (non-decreasing) क्रम में।
service: हर ग्राहक की सेवा के मिनट, उसी क्रम में।
tellers: कैशियरों की संख्या।
आउटपुट
[total_wait, longest_wait, last_finish] लौटाइए: सभी इंतज़ारों का योग, किसी एक का सबसे लंबा इंतज़ार, और वह मिनट जब आख़िरी ग्राहक का काम ख़त्म होता है। कोई ग्राहक न हो तो [0, 0, 0] लौटाइए।
सीमाएँ
0 ≤ ग्राहकों की संख्या ≤ 2,000
0 ≤ आने का समय ≤ 100,000
1 ≤ सेवा का समय ≤ 1,000
1 ≤ tellers ≤ 20
उदाहरण
इनपुट:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2
अपेक्षित आउटपुट:
expected = [4, 2, 8]
इनपुट:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;
अपेक्षित आउटपुट:
std::vector<long long> expected = {4, 2, 8};
इनपुट:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;
अपेक्षित आउटपुट:
long[] expected = new long[] {4, 2, 8};
व्याख्या
ग्राहक 1 और 2 तुरंत शुरू करते हैं (0 और 1 पर)। कैशियर 2 मिनट 4 पर ख़ाली होता है, इसलिए ग्राहक 3 को 2 मिनट इंतज़ार करना पड़ता है; कैशियर 1 मिनट 5 पर ख़ाली होता है, इसलिए ग्राहक 4 भी 2 मिनट इंतज़ार करता है। आख़िरी काम max(8, 7) = 8 पर ख़त्म होता है: [4, 2, 8]।
इनपुट:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1
अपेक्षित आउटपुट:
expected = [12, 8, 12]
इनपुट:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;
अपेक्षित आउटपुट:
std::vector<long long> expected = {12, 8, 12};
इनपुट:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;
अपेक्षित आउटपुट:
long[] expected = new long[] {12, 8, 12};
व्याख्या
एक कैशियर होने पर इंतज़ार 0, 4 और 8 मिनट हैं, और आख़िरी ग्राहक 12 पर फ़ारिग होता है: [12, 8, 12]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
एक array रखिए जिसमें हो कि हर कैशियर किस मिनट ख़ाली होता है।
संकेत 2
हर ग्राहक के लिए सबसे पहले ख़ाली होने वाला समय चुनिए (बराबरी होने पर सबसे छोटा index)।
संकेत 3
शुरू होने का समय आने के समय और उस ख़ाली होने के समय में से जो बाद में हो, वह है; इंतज़ार है शुरू घटा आना।
अपेक्षित जटिलता
समय O(n × k), अतिरिक्त स्थान O(k)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।