Problema
Com async/await você pode iniciar várias tarefas e deixá-las executar ao mesmo tempo. Um SemaphoreSlim frequentemente limita quantas executam ao mesmo tempo.
Tarefas numeradas de 0 a n − 1 levam durations[i] unidades de tempo. No tempo 0, inicie o máximo de tarefas que o limite permitir, em ordem de índice. Sempre que tarefas terminarem, registre-as (se várias terminarem no mesmo instante, menor índice primeiro) e imediatamente inicie as próximas tarefas aguardando, em ordem de índice, para preencher os slots livres.
Implemente parallel_task_order(durations, limit).
Input
durations: Quanto tempo cada tarefa leva.
limit: O número máximo de tarefas executando ao mesmo tempo.
Output
Retorne os índices das tarefas na ordem em que elas terminam.
Restrições
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
Exemplos
Entrada:
limit = 2
durations = [4, 2, 3, 1]
Saída esperada:
expected = [1, 0, 2, 3]Entrada:
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
Saída esperada:
std::vector<long long> expected = {1, 0, 2, 3};Entrada:
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
Saída esperada:
long[] expected = new long[] {1, 0, 2, 3};Explicação
As tarefas 0 e 1 começam. A tarefa 1 termina em 2 e a tarefa 2 começa (termina em 5). A tarefa 0 termina em 4 e a tarefa 3 começa (termina em 5). As tarefas 2 e 3 terminam juntas, menor índice primeiro: [1, 0, 2, 3].
Entrada:
limit = 3
durations = [3, 1, 2]
Saída esperada:
expected = [1, 2, 0]Entrada:
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
Saída esperada:
std::vector<long long> expected = {1, 2, 0};Entrada:
long limit = 3;
long[] durations = new long[] {3, 1, 2};
Saída esperada:
long[] expected = new long[] {1, 2, 0};Explicação
Todas as tarefas executam ao mesmo tempo e terminam em 1, 2 e 3: [1, 2, 0].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Mantenha as tarefas em execução ordenadas pelo horário de término e depois pelo índice.
Dica 2
A cada passo, pule para o próximo horário de término e colete todas as tarefas que terminam nele.
Dica 3
Preencha as vagas livres com as próximas tarefas em espera, por índice.
Complexidade esperada
tempo O(n log limit), espaço extra O(limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.