Problema
Con async/await puoi avviare diversi task e lasciarli eseguire contemporaneamente. Un SemaphoreSlim spesso limita quanti possono girare alla volta.
I task numerati da 0 a n − 1 richiedono durations[i] unità di tempo. Al tempo 0 avvia quanti task consente il limite, in ordine di indice. Ogni volta che dei task terminano, registrali (se più task finiscono nello stesso istante, prima l'indice più basso) e avvia immediatamente i task in attesa successivi, in ordine di indice, per riempire gli slot liberi.
Implementa parallel_task_order(durations, limit).
Input
durations: Quanto tempo impiega ciascun task.
limit: Il numero massimo di task in esecuzione nello stesso momento.
Output
Restituisci gli indici dei task nell'ordine in cui terminano.
Vincoli
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
Esempi
Input:
limit = 2
durations = [4, 2, 3, 1]
Output atteso:
expected = [1, 0, 2, 3]Input:
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
Output atteso:
std::vector<long long> expected = {1, 0, 2, 3};Input:
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
Output atteso:
long[] expected = new long[] {1, 0, 2, 3};Spiegazione
I task 0 e 1 partono. Il task 1 termina a 2 e il task 2 parte (termina a 5). Il task 0 termina a 4 e il task 3 parte (termina a 5). I task 2 e 3 finiscono insieme, prima l'indice più basso: [1, 0, 2, 3].
Input:
limit = 3
durations = [3, 1, 2]
Output atteso:
expected = [1, 2, 0]Input:
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
Output atteso:
std::vector<long long> expected = {1, 2, 0};Input:
long limit = 3;
long[] durations = new long[] {3, 1, 2};
Output atteso:
long[] expected = new long[] {1, 2, 0};Spiegazione
Tutti i task girano contemporaneamente e terminano a 1, 2 e 3: [1, 2, 0].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Tieni i task in esecuzione ordinati per ora di fine e poi per indice.
Suggerimento 2
A ogni passo salta alla prossima ora di fine e raccogli tutti i task che finiscono in quel momento.
Suggerimento 3
Riempi i posti liberi con i task in attesa successivi, per indice.
Complessità attesa
tempo O(n log limit), spazio aggiuntivo O(limit)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.