Task Scheduler

Q: Wie hoch ist die zeitliche Komplexität des Task Schedulers?

Das Zählen der Buchstaben benötigt für m Aufgaben O(m) , und die Formel liest dann 26 Zählwerte. Die Lösung benötigt daher O(m) Zeit und O(1) zusätzlichen Speicher. Die Simulation mit einem Max-Heap entnimmt für jede Aufgabe einmal ein Element und benötigt O(m log k) , wobei k ≤ 26 Buchstaben gilt.

Q: Wann benötigt der Task Scheduler keine Leerlaufzeit?

Wenn m ≥ (top-1) × (n+1) + atTop , füllen die Aufgaben jeden freien Platz und dehnen die Rahmen, anstatt Lücken zu lassen, also lautet die Antwort m . Beispiel 2, "ABCABD" mit n = 1 , ist ein solcher Fall.

MittelGreedy Heap Hashing

+10

Du erhältst die Zeichenfolge tasks aus Großbuchstaben, wobei jeder Buchstabe für eine Aufgabe steht, und eine ganze Zahl n. Ein Prozessor führt pro Zeiteinheit eine Aufgabe in beliebiger Reihenfolge deiner Wahl aus oder bleibt eine Zeiteinheit untätig.

Zwischen zwei Ausführungen desselben Buchstabens müssen mindestens n Zeiteinheiten liegen: Ein Buchstabe, der in Zeiteinheit t ausgeführt wird, kann frühestens in Zeiteinheit t+n+1 erneut ausgeführt werden. Gib die geringste Anzahl an Zeiteinheiten zurück, in der alle Aufgaben ausgeführt werden.

Funktion

leastInterval(tasks: string, n: integer) → integer

tasksstring: die Aufgaben, jeweils ein Großbuchstabe
ninteger: die geringste Anzahl von Einheiten zwischen zwei Vorkommen desselben Buchstabens
Gibt zurückinteger: die geringstmögliche Anzahl an Einheiten, einschließlich untätiger Einheiten

Einschränkungen

1 ≤ tasks.length ≤ 10⁴
tasks enthält nur die Großbuchstaben A bis Z.
0 ≤ n ≤ 100

Beispiele

Eingabe: tasks = "CACBAC"n = 2
Ausgabe: 7
Erklärung: C läuft dreimal mit zwei Einheiten zwischen den Läufen, daher umfassen allein seine Läufe 7 Einheiten. Die Reihenfolge C A B C A, Leerlauf, C füllt die Lücken mit A und B und benötigt eine Leerlaufeinheit: 7.

Eingabe: tasks = "ABCABD"n = 1
Ausgabe: 6
Erklärung: A und B werden jeweils zweimal ausgeführt, mit einer Einheit zwischen den Ausführungen. Die Reihenfolge A B C A B D hält sie auseinander, ohne dass eine Einheit ungenutzt bleibt. Die Antwort ist also die Anzahl der Aufgaben: 6.

Eingabe: tasks = "ZZZ"n = 3
Ausgabe: 9
Erklärung: Nur Z muss ausgeführt werden, daher ist jede Lücke ungenutzt: Z, drei ungenutzte Einheiten, Z, drei ungenutzte Einheiten, Z. Das sind 9 Einheiten.

Weiterführende Frage

Kannst du auch einen Zeitplan kürzester Länge als Zeichenfolge zurückgeben, mit einem . für jede Leerlaufeinheit?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Du bestimmst die Reihenfolge, daher ist die Frage, wie wenige Leerlaufeinheiten du brauchst. Der Buchstabe mit der höchsten Häufigkeit entscheidet: Seine Vorkommen müssen n+1 Einheiten auseinanderliegen, und die anderen Aufgaben füllen die Lücken dazwischen. Führe zuerst die Buchstaben mit der höchsten Häufigkeit mithilfe eines Max-Heaps aus oder zähle die Lücken direkt mit einer einzigen Formel.

Runden mit einem Max-Heap simulieren

Idee

Teile die Zeit in Runden von n+1 Einheiten ein. Kein Buchstabe darf innerhalb einer Runde zweimal ausgeführt werden, und ein Buchstabe an einem bestimmten Platz einer Runde darf in der nächsten Runde wieder am selben Platz ausgeführt werden, genau n+1 Einheiten später. Führe in jeder Runde die Buchstaben mit den meisten verbleibenden Vorkommen aus. Ihre verbleibenden Ausführungen müssen mindestens n+1 Einheiten auseinanderliegen, daher können sie am Ende Leerlaufzeit erzwingen; wenn du sie zuerst ausführst, bleiben die Anzahlen ausgeglichen.

Eine Runde, nach der noch Arbeit übrig ist, dauert n+1 Einheiten; ihre leeren Plätze sind Leerlaufzeit. Die letzte Runde dauert nur so lange wie die darin ausgeführten Aufgaben. In Beispiel 1 werden in den Runden zuerst C A B ausgeführt, dann C A und eine Leerlaufeinheit, dann als Letztes C: 3 + 3 + 1 = 7. Jeder Pop führt eine Aufgabe aus, daher beträgt die Laufzeit bei m Aufgaben und k ≤ 26 Buchstaben O(m log k).

Algorithmus

Zähle jeden Buchstaben und füge die Zählwerte, die größer als null sind, in einen Max-Heap ein.
Solange der Heap nicht leer ist, führe eine Runde aus: Entnimm bis zu n+1 Zählwerte und behalte jeden Zählwert minus eins, der weiterhin größer als null ist.
Füge die beibehaltenen Zählwerte wieder hinzu.
Addiere n+1 zur Zeit, wenn der Heap nicht leer ist; andernfalls addiere die Anzahl der Aufgaben, die in der Runde ausgeführt wurden.
Gib die Zeit zurück.

import heapq
from collections import Counter


def leastInterval(tasks, n):
    # heapq is a min-heap, so store negated counts to pop the largest first.
    heap = [-c for c in Counter(tasks).values()]
    heapq.heapify(heap)
    time = 0
    while heap:
        # One round of n+1 slots: run the most frequent tasks left, each at most once.
        left = []
        ran = 0
        while ran < n + 1 and heap:
            c = -heapq.heappop(heap)
            ran += 1
            if c > 1:
                left.append(c - 1)
        for c in left:
            heapq.heappush(heap, -c)
        # A round lasts n+1 units, idle included; the last one ends with its last task.
        time += n + 1 if heap else ran
    return time

Zähle die Vorkommen des häufigsten Buchstabens

Idee

Sei top die höchste Anzahl, die der Buchstabe X erreicht. Ordne X so an, dass nach jedem Durchlauf außer dem letzten n freie Plätze bleiben: top-1 Abschnitte mit jeweils n+1 Einheiten, gefolgt von X' letztem Durchlauf. Ein Buchstabe, der weniger als top Mal vorkommt, passt in die freien Plätze, eine Kopie pro Abschnitt, sodass seine Kopien mindestens n+1 Einheiten voneinander entfernt bleiben. Jeder andere Buchstabe mit top Kopien fügt am Ende eine Einheit hinzu. Bei atTop Buchstaben mit der höchsten Anzahl sind das (top-1) × (n+1) + atTop Einheiten.

Kein Zeitplan ist kürzer: Teile die ersten (top-1) × (n+1) Einheiten in top-1 Zeitfenster von jeweils n+1 Einheiten auf. Jeder Buchstabe mit der höchsten Anzahl kommt in jedem Zeitfenster höchstens einmal vor, daher hat jeder der atTop Buchstaben nach den Zeitfenstern noch einen Durchlauf übrig. Gibt es mehr Aufgaben als freie Plätze, lass einige Abschnitte länger als n+1 werden. Ein längerer Abschnitt vergrößert die Abstände nur, sodass nichts untätig bleibt und die Antwort m ist. Die Antwort ist der größere der beiden Werte.

Algorithmus

Zähle jeden der 26 Buchstaben.
Finde top, die höchste Anzahl, und atTop, wie viele Buchstaben diese Anzahl haben.
Berechne frames = (top-1) × (n+1) + atTop.
Gib den größeren Wert von frames und der Anzahl der Aufgaben zurück.

def leastInterval(tasks, n):
    counts = [0] * 26
    for ch in tasks:
        counts[ord(ch) - ord("A")] += 1
    top = max(counts)
    at_top = counts.count(top)  # tasks that share the highest count
    # top-1 full frames of n+1 units, then one last slot per task at the top count.
    frames = (top - 1) * (n + 1) + at_top
    # With more tasks than frame slots, no idle unit is needed at all.
    return max(frames, len(tasks))

Stolperfallen und Grenzfälle

Die Buchstaben vergessen, die an der Spitze gleichauf liegen. In "MMNNPP" haben bei n = 5 alle drei Buchstaben den Zählerstand 2. Die Antwort lautet also (2-1) × 6 + 3 = 9, nicht 7.
Den Schritt mit dem größeren Wert vergessen. In Beispiel 2 ergeben die Zeitfenster (2-1) × 2 + 2 = 4, aber sechs Aufgaben benötigen sechs Zeiteinheiten.
Die letzte Runde mit vollen n+1 Zeiteinheiten berechnen. Nach der letzten Aufgabe muss nichts warten: Beispiel 3 würde 12 statt 9 ergeben.
Einen Zählerstand noch innerhalb der Runde zurücklegen. Dann kann derselbe Buchstabe in dieser Runde erneut entnommen und zweimal in zu kurzem Abstand ausgeführt werden.

Häufige Fragen3

Wie hoch ist die zeitliche Komplexität des Task Schedulers?

Das Zählen der Buchstaben benötigt für m Aufgaben O(m), und die Formel liest dann 26 Zählwerte. Die Lösung benötigt daher O(m) Zeit und O(1) zusätzlichen Speicher. Die Simulation mit einem Max-Heap entnimmt für jede Aufgabe einmal ein Element und benötigt O(m log k), wobei k ≤ 26 Buchstaben gilt.

Wann benötigt der Task Scheduler keine Leerlaufzeit?

Wenn m ≥ (top-1) × (n+1) + atTop, füllen die Aufgaben jeden freien Platz und dehnen die Rahmen, anstatt Lücken zu lassen, also lautet die Antwort m. Beispiel 2, "ABCABD" mit n = 1, ist ein solcher Fall.

Spielt die Reihenfolge der Eingabezeichenfolge eine Rolle?

Nein. Du bestimmst die Reihenfolge, in der der Prozessor die Aufgaben ausführt, daher zählt nur, wie oft jeder Buchstabe vorkommt. "CACBAC" und "CCCAAB" benötigen bei n = 2 beide 7 Einheiten.

def leastInterval(tasks, n):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

tasks = "CACBAC"
n = 2

Erwartete Ausgabe