Problème
Avec async/await vous pouvez lancer plusieurs tâches et les laisser s'exécuter en même temps. Un SemaphoreSlim limite souvent combien peuvent tourner à la fois.
Les tâches numérotées de 0 à n − 1 prennent durations[i] unités de temps. Au temps 0, lancez autant de tâches que la limite le permet, dans l'ordre des indices. Chaque fois que des tâches se terminent, enregistrez-les (si plusieurs se terminent au même moment, le plus petit indice d'abord) et lancez immédiatement les prochaines tâches en attente, dans l'ordre des indices, pour remplir les emplacements libres.
Implémentez parallel_task_order(durations, limit).
Entrée
durations: La durée de chaque tâche.
limit: Le nombre maximum de tâches exécutées en même temps.
Sortie
Retournez les indices des tâches dans l'ordre où elles se terminent.
Contraintes
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
Exemples
Entrée :
limit = 2
durations = [4, 2, 3, 1]
Sortie attendue :
expected = [1, 0, 2, 3]Entrée :
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
Sortie attendue :
std::vector<long long> expected = {1, 0, 2, 3};Entrée :
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
Sortie attendue :
long[] expected = new long[] {1, 0, 2, 3};Explication
Les tâches 0 et 1 démarrent. La tâche 1 se termine à 2 et la tâche 2 démarre (elle se termine à 5). La tâche 0 se termine à 4 et la tâche 3 démarre (elle se termine à 5). Les tâches 2 et 3 se terminent en même temps, le plus petit indice d'abord : [1, 0, 2, 3].
Entrée :
limit = 3
durations = [3, 1, 2]
Sortie attendue :
expected = [1, 2, 0]Entrée :
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
Sortie attendue :
std::vector<long long> expected = {1, 2, 0};Entrée :
long limit = 3;
long[] durations = new long[] {3, 1, 2};
Sortie attendue :
long[] expected = new long[] {1, 2, 0};Explication
Toutes les tâches s'exécutent en même temps et se terminent à 1, 2 et 3 : [1, 2, 0].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Gardez les tâches en cours triées par heure de fin, puis par indice.
Indice 2
À chaque étape, sautez à la prochaine heure de fin et récupérez toutes les tâches qui finissent alors.
Indice 3
Remplissez les places libres avec les tâches en attente suivantes, par indice.
Complexité attendue
temps O(n log limit), espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.