Parallel Task Completion Order

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};

Ввод:
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};

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

• Microsoft Learn, Asynchronous programming with async and await