समस्या
async/await के साथ आप कई tasks start कर सकते हैं और उन्हें एक ही समय पर चलने दे सकते हैं. SemaphoreSlim अक्सर इस बात को limit करता है कि एक साथ कितने चलेंगे.
0 से n − 1 तक numbered tasks को durations[i] time units लगते हैं. समय 0 पर, index order में, जितने tasks limit allow करे उतने start करें. जब भी tasks finish हों, उन्हें record करें (अगर कई एक ही moment पर finish हों, तो lower index first) और तुरंत next waiting tasks को, index order में, free slots भरने के लिए start करें.
parallel_task_order(durations, limit) implement करें.
Input
durations: Each task कितनी देर लेता है.
limit: एक ही समय पर चलने वाले tasks की maximum संख्या.
Output
Return the task indices in the order they finish.
सीमाएँ
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
उदाहरण
इनपुट:
limit = 2
durations = [4, 2, 3, 1]
अपेक्षित आउटपुट:
expected = [1, 0, 2, 3]इनपुट:
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
अपेक्षित आउटपुट:
std::vector<long long> expected = {1, 0, 2, 3};इनपुट:
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
अपेक्षित आउटपुट:
long[] expected = new long[] {1, 0, 2, 3};व्याख्या
Tasks 0 और 1 start होते हैं. Task 1 2 पर end होता है और task 2 start होता है (5 पर ends). Task 0 4 पर end होता है और task 3 start होता है (5 पर ends). Tasks 2 और 3 साथ finish करते हैं, lower index first: [1, 0, 2, 3].
इनपुट:
limit = 3
durations = [3, 1, 2]
अपेक्षित आउटपुट:
expected = [1, 2, 0]इनपुट:
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
अपेक्षित आउटपुट:
std::vector<long long> expected = {1, 2, 0};इनपुट:
long limit = 3;
long[] durations = new long[] {3, 1, 2};
अपेक्षित आउटपुट:
long[] expected = new long[] {1, 2, 0};व्याख्या
All tasks एक साथ run होते हैं और 1, 2 और 3 पर finish होते हैं: [1, 2, 0].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
चल रहे टास्क को खत्म होने के समय, फिर इंडेक्स के क्रम में रखें।
संकेत 2
हर कदम पर अगले खत्म होने के समय पर जाएँ और तब खत्म होने वाले सभी टास्क लें।
संकेत 3
खाली जगहों को इंतज़ार कर रहे अगले टास्क से इंडेक्स के क्रम में भरें।
अपेक्षित जटिलता
समय O(n log limit), अतिरिक्त स्थान O(limit)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।