Problem
Mit async/await kannst du mehrere Aufgaben starten und sie gleichzeitig laufen lassen. Ein SemaphoreSlim begrenzt oft, wie viele gleichzeitig laufen.
Aufgaben mit den Nummern 0 bis n − 1 benötigen durations[i] Zeiteinheiten. Starte zur Zeit 0 so viele Aufgaben, wie die Begrenzung erlaubt, in Indexreihenfolge. Immer wenn Aufgaben fertig werden, notiere sie (wenn mehrere im selben Moment fertig werden, zuerst den kleineren Index) und starte sofort die nächsten wartenden Aufgaben, wieder in Indexreihenfolge, um die freien Plätze zu füllen.
Implementiere parallel_task_order(durations, limit).
Input
durations: Wie lange jede Aufgabe dauert.
limit: Die maximale Anzahl von Aufgaben, die gleichzeitig laufen.
Output
Gib die Aufgabenindizes in der Reihenfolge zurück, in der sie fertig werden.
Einschränkungen
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
Beispiele
Eingabe:
limit = 2
durations = [4, 2, 3, 1]
Erwartete Ausgabe:
expected = [1, 0, 2, 3]Eingabe:
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
Erwartete Ausgabe:
std::vector<long long> expected = {1, 0, 2, 3};Eingabe:
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
Erwartete Ausgabe:
long[] expected = new long[] {1, 0, 2, 3};Erläuterung
Die Aufgaben 0 und 1 starten. Aufgabe 1 endet bei 2 und Aufgabe 2 startet (endet bei 5). Aufgabe 0 endet bei 4 und Aufgabe 3 startet (endet bei 5). Die Aufgaben 2 und 3 beenden gleichzeitig, zuerst der kleinere Index: [1, 0, 2, 3].
Eingabe:
limit = 3
durations = [3, 1, 2]
Erwartete Ausgabe:
expected = [1, 2, 0]Eingabe:
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
Erwartete Ausgabe:
std::vector<long long> expected = {1, 2, 0};Eingabe:
long limit = 3;
long[] durations = new long[] {3, 1, 2};
Erwartete Ausgabe:
long[] expected = new long[] {1, 2, 0};Erläuterung
Alle Aufgaben laufen gleichzeitig und enden bei 1, 2 und 3: [1, 2, 0].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Halte die laufenden Tasks nach Endzeit und dann nach Index sortiert.
Hinweis 2
Springe in jedem Schritt zur nächsten Endzeit und sammle alle Tasks, die dann enden.
Hinweis 3
Fülle freie Plätze mit den nächsten wartenden Tasks in Indexreihenfolge.
Erwartete Komplexität
Zeit O(n log limit), zusätzlicher Speicher O(limit)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.