Task Scheduler

Q: Jaka jest złożoność czasowa Task Scheduler?

Policzenie liter zajmuje O(m) dla m zadań, a następnie wzór odczytuje 26 liczników, więc rozwiązanie działa w czasie O(m) i wymaga O(1) dodatkowej pamięci. Symulacja z użyciem kopca maksymalnego wykonuje jedno usunięcie na zadanie, czyli ma złożoność O(m log k) , gdzie k ≤ 26 liter.

Q: Kiedy Harmonogram zadań nie potrzebuje czasu bezczynności?

Gdy m ≥ (top-1) × (n+1) + atTop , zadania wypełniają wszystkie wolne miejsca i wydłużają przedziały zamiast pozostawiać luki, więc odpowiedzią jest m . Przykład 2, "ABCABD" przy n = 1 , to taki przypadek.

ŚrednieAlgorytmy zachłanne Kopiec Haszowanie

+10

Otrzymujesz ciąg znaków tasks składający się z wielkich liter, po jednej literze na zadanie, oraz liczbę całkowitą n. Procesor wykonuje jedno zadanie na jednostkę czasu, w dowolnej wybranej przez Ciebie kolejności, albo pozostaje bezczynny przez jedną jednostkę czasu.

Między dwoma wykonaniami zadań oznaczonych tą samą literą musi upłynąć co najmniej n jednostek: zadanie wykonane w jednostce t może zostać ponownie wykonane najwcześniej w jednostce t+n+1. Zwróć najmniejszą liczbę jednostek czasu potrzebną do wykonania każdego zadania.

Funkcja

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

tasksstring: zadania, po jednej wielkiej literze każde
ninteger: najmniejsza liczba jednostek między dwoma wystąpieniami tej samej litery
Zwracainteger: najmniejsza liczba jednostek, wliczając bezczynne

Ograniczenia

1 ≤ tasks.length ≤ 10⁴
tasks zawiera tylko wielkie litery od A do Z.
0 ≤ n ≤ 100

Przykłady

Wejście: tasks = "CACBAC"n = 2
Wyjście: 7
Wyjaśnienie: C wykonuje się trzy razy, z dwiema jednostkami między wykonaniami, więc same jego wykonania zajmują 7 jednostek. Kolejność C A B C A, bezczynność, C wypełnia przerwy za pomocą A i B i wymaga jednej jednostki bezczynności: 7.

Wejście: tasks = "ABCABD"n = 1
Wyjście: 6
Wyjaśnienie: A i B wykonują się po dwa razy, z jedną jednostką pomiędzy kolejnymi wykonaniami. Kolejność A B C A B D rozdziela je bez żadnej bezczynnej jednostki, więc odpowiedzią jest liczba zadań: 6.

Wejście: tasks = "ZZZ"n = 3
Wyjście: 9
Wyjaśnienie: Do uruchomienia jest tylko Z, więc każda przerwa jest bezczynna: Z, trzy bezczynne jednostki, Z, trzy bezczynne jednostki, Z. To 9 jednostek.

Pytanie dodatkowe

Czy możesz również zwrócić jeden harmonogram o najmniejszej długości jako ciąg znaków z . dla każdej bezczynnej jednostki?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

To ty wybierasz kolejność, więc pytanie brzmi, ilu jak najmniej jednostek bezczynności potrzebujesz. Decyduje najczęściej występująca litera: jej wystąpienia muszą być oddalone od siebie o n+1 jednostek, a pozostałe zadania wypełniają przerwy między nimi. Najpierw wykonuj zadania z najczęściej występującymi literami, używając kopca maksymalnego, albo bezpośrednio policz przerwy za pomocą jednego wzoru.

Symuluj rundy za pomocą kopca maksymalnego

Intuicja

Podziel czas na rundy po n+1 jednostek. Żadna litera nie może wystąpić dwa razy w rundzie, a litera na danej pozycji w jednej rundzie może wystąpić ponownie na tej samej pozycji w następnej, dokładnie n+1 jednostek później. W każdej rundzie wykonuj zadania odpowiadające literom, których kopii pozostało najwięcej. Odstępy między ich pozostałymi wystąpieniami muszą wynosić n+1, więc to one mogą wymusić bezczynność na końcu; wykonywanie ich jako pierwszych utrzymuje wyrównany poziom liczników.

Runda, po której pozostają jeszcze zadania do wykonania, kosztuje n+1 jednostek, a jej puste miejsca oznaczają bezczynność; ostatnia runda kosztuje tylko tyle jednostek, ile zadań w niej wykonano. W przykładzie 1 rundy obejmują kolejno C A B, potem C A i jedną jednostkę bezczynności, a na końcu samo C: 3 + 3 + 1 = 7. Każde zdjęcie elementu z kolejki wykonuje jedno zadanie, więc przy m zadaniach i k ≤ 26 literach złożoność wynosi O(m log k).

Algorytm

Policz wystąpienia każdej litery i umieść liczby większe od zera w kopcu maksymalnym.
Dopóki kopiec nie jest pusty, wykonaj rundę: zdejmij maksymalnie n+1 liczników i zachowaj te pomniejszone o jeden, które nadal są większe od zera.
Włóż zachowane liczniki z powrotem.
Dodaj n+1 do czasu, jeśli kopiec nie jest pusty; w przeciwnym razie dodaj liczbę zadań wykonanych w rundzie.
Zwróć czas.

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

Policz wystąpienia najczęściej pojawiającej się litery

Intuicja

Niech top oznacza największą liczbę wystąpień, którą ma litera X. Rozmieść X tak, aby po każdym ciągu oprócz ostatniego było n wolnych miejsc: top-1 bloków po n+1 jednostek, a następnie ostatni ciąg X. Litera występująca mniej niż top razy zmieści się w wolnych miejscach — po jednym wystąpieniu w każdym bloku — więc odstępy między jej wystąpieniami będą wynosić co najmniej n+1. Każda inna litera występująca top razy dodaje jedną jednostkę na końcu. Jeśli atTop liter występuje najczęściej, otrzymujemy (top-1) × (n+1) + atTop jednostek.

Żaden harmonogram nie może być krótszy: podziel pierwsze (top-1) × (n+1) jednostek na top-1 okien po n+1. Każda najczęściej występująca litera pojawia się w każdym oknie najwyżej raz, więc po tych oknach każdej z atTop liter pozostanie jeszcze jedno wystąpienie. Jeśli zadań jest więcej niż wolnych miejsc, wydłuż niektóre bloki ponad n+1. Dłuższy blok tylko zwiększa odstępy, więc nie ma bezczynności, a odpowiedzią jest m. Odpowiedź to większa z tych dwóch wartości.

Algorytm

Policz każdą z 26 liter.
Znajdź top, największą liczbę, oraz atTop, liczbę liter, które ją mają.
Oblicz frames = (top-1) × (n+1) + atTop.
Zwróć większą z wartości: frames i liczby zadań.

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))

Pułapki i przypadki brzegowe

Zapomnienie o literach, które remisują na pierwszym miejscu. W "MMNNPP" przy n = 5 każda z trzech liter występuje 2 razy, więc odpowiedzią jest (2-1) × 6 + 3 = 9, a nie 7.
Zapomnienie o kroku wyboru większej wartości. W przykładzie 2 ramki dają (2-1) × 2 + 2 = 4, ale sześć zadań wymaga sześciu jednostek.
Przypisanie ostatniej rundzie pełnych n+1 jednostek. Po ostatnim zadaniu nic nie czeka: w przykładzie 3 wynik wyniósłby 12 zamiast 9.
Przeniesienie liczby z powrotem do tej samej rundy. Ta sama litera może wtedy zostać ponownie zdjęta w tej rundzie i wykonana dwukrotnie w zbyt krótkim odstępie.

Najczęstsze pytania3

Jaka jest złożoność czasowa Task Scheduler?

Policzenie liter zajmuje O(m) dla m zadań, a następnie wzór odczytuje 26 liczników, więc rozwiązanie działa w czasie O(m) i wymaga O(1) dodatkowej pamięci. Symulacja z użyciem kopca maksymalnego wykonuje jedno usunięcie na zadanie, czyli ma złożoność O(m log k), gdzie k ≤ 26 liter.

Kiedy Harmonogram zadań nie potrzebuje czasu bezczynności?

Gdy m ≥ (top-1) × (n+1) + atTop, zadania wypełniają wszystkie wolne miejsca i wydłużają przedziały zamiast pozostawiać luki, więc odpowiedzią jest m. Przykład 2, "ABCABD" przy n = 1, to taki przypadek.

Czy kolejność znaków w ciągu wejściowym ma znaczenie?

Nie. To ty wybierasz kolejność, w jakiej procesor wykonuje zadania, więc liczy się tylko to, ile razy występuje każda litera. "CACBAC" i "CCCAAB" przy n = 2 wymagają po 7 jednostek.

def leastInterval(tasks, n):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

tasks = "CACBAC"
n = 2

Oczekiwany wynik