समस्या
With async/await you can start several tasks and let them run at the same time. A SemaphoreSlim often caps how many run at once.
Tasks numbered 0 to n − 1 take durations[i] time units. At time 0 start as many tasks as the limit allows, in index order. Whenever tasks finish, record them (if several finish at the same moment, lower index first) and immediately start the next waiting tasks, in index order, to fill the free slots.
Implement parallel_task_order(durations, limit).
Input
durations: How long each task takes.
limit: The maximum number of tasks running at the same time.
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 and 1 start. Task 1 ends at 2 and task 2 starts (ends at 5). Task 0 ends at 4 and task 3 starts (ends at 5). Tasks 2 and 3 finish together, 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 at once and finish at 1, 2 and 3: [1, 2, 0].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Keep the running tasks ordered by finish time, then by index.
संकेत 2
Each step jumps to the next finish time and collects every task ending then.
संकेत 3
Refill free slots with the next waiting tasks in index order.
अपेक्षित जटिलता
O(n log limit) time, O(limit) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।