Problema
Con async/await puedes iniciar varias tareas y dejarlas ejecutarse al mismo tiempo. Un SemaphoreSlim suele limitar cuántas se ejecutan a la vez.
Las tareas numeradas de 0 a n − 1 tardan durations[i] unidades de tiempo. En el tiempo 0, inicia tantas tareas como permita el límite, en orden de índice. Cada vez que terminen tareas, regístralas (si varias terminan en el mismo momento, primero la de menor índice) e inicia inmediatamente las siguientes tareas en espera, en orden de índice, para llenar los huecos libres.
Implementa parallel_task_order(durations, limit).
Entrada
durations: Cuánto tarda cada tarea.
limit: El número máximo de tareas ejecutándose al mismo tiempo.
Salida
Devuelve los índices de las tareas en el orden en que terminan.
Restricciones
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
Ejemplos
Entrada:
limit = 2
durations = [4, 2, 3, 1]
Salida esperada:
expected = [1, 0, 2, 3]Entrada:
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
Salida esperada:
std::vector<long long> expected = {1, 0, 2, 3};Entrada:
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
Salida esperada:
long[] expected = new long[] {1, 0, 2, 3};Explicación
Las tareas 0 y 1 empiezan. La tarea 1 termina en 2 y la tarea 2 empieza (termina en 5). La tarea 0 termina en 4 y la tarea 3 empieza (termina en 5). Las tareas 2 y 3 terminan a la vez, primero la de menor índice: [1, 0, 2, 3].
Entrada:
limit = 3
durations = [3, 1, 2]
Salida esperada:
expected = [1, 2, 0]Entrada:
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
Salida esperada:
std::vector<long long> expected = {1, 2, 0};Entrada:
long limit = 3;
long[] durations = new long[] {3, 1, 2};
Salida esperada:
long[] expected = new long[] {1, 2, 0};Explicación
Todas las tareas se ejecutan a la vez y terminan en 1, 2 y 3: [1, 2, 0].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Mantén las tareas en marcha ordenadas por hora de fin y luego por índice.
Pista 2
En cada paso salta a la siguiente hora de fin y recoge todas las tareas que terminan entonces.
Pista 3
Llena los huecos libres con las siguientes tareas en espera, por índice.
Complejidad esperada
tiempo O(n log limit), espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.