Task Scheduler

Q: Qual è la complessità temporale di Task Scheduler?

Contare le lettere richiede O(m) per m attività, e poi la formula legge 26 conteggi, quindi la soluzione richiede O(m) tempo e O(1) memoria aggiuntiva. La simulazione con max-heap esegue un'estrazione per attività: O(m log k) con k ≤ 26 lettere.

Q: Quando Task Scheduler non richiede tempo di inattività?

Quando m ≥ (top-1) × (n+1) + atTop , le attività riempiono ogni slot libero e allungano i frame invece di lasciare spazi vuoti, quindi la risposta è m . L’esempio 2, "ABCABD" con n = 1 , è un caso del genere.

MedioGreedy Heap Hashing

+10

Ti viene data una stringa tasks composta da lettere maiuscole, una lettera per attività, e un intero n. Un processore esegue un'attività per unità di tempo, nell'ordine che scegli, oppure rimane inattivo per un'unità.

Tra due esecuzioni della stessa lettera devono trascorrere almeno n unità: una lettera eseguita all'unità t può essere eseguita di nuovo non prima dell'unità t+n+1. Restituisci il numero minimo di unità necessario per eseguire tutte le attività.

Funzione

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

tasksstring: i compiti, una lettera maiuscola ciascuno
ninteger: il minor numero di unità tra due occorrenze della stessa lettera
Restituisceinteger: il minor numero di unità, comprese quelle inattive

Vincoli

1 ≤ tasks.length ≤ 10⁴
tasks contiene solo le lettere maiuscole da A a Z.
0 ≤ n ≤ 100

Esempi

Input: tasks = "CACBAC"n = 2
Output: 7
Spiegazione: C viene eseguito tre volte con due unità tra un'esecuzione e l'altra, quindi le sue sole esecuzioni coprono 7 unità. L'ordine C A B C A, inattivo, C riempie gli intervalli con A e B e richiede un'unità di inattività: 7.

Input: tasks = "ABCABD"n = 1
Output: 6
Spiegazione: A e B vengono eseguiti due volte ciascuno, con un'unità tra un'esecuzione e l'altra. L'ordine A B C A B D li mantiene separati senza unità inattive, quindi la risposta è il numero di attività, 6.

Input: tasks = "ZZZ"n = 3
Output: 9
Spiegazione: C'è solo Z da eseguire, quindi ogni intervallo è inattivo: Z, tre unità inattive, Z, tre unità inattive, Z. Sono 9 unità.

Per approfondire

Puoi restituire anche una pianificazione di lunghezza minima, come stringa con un . per ogni unità inattiva?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Scegli tu l’ordine, quindi la domanda è quanti meno unità inattive ti servono. Lo determina la lettera più frequente: le sue occorrenze devono distare n+1 unità, e gli altri task riempiono gli spazi tra di esse. Esegui prima le lettere più frequenti usando un max-heap, oppure conta direttamente gli spazi con un’unica formula.

Simula i turni con un heap massimo

Intuizione

Dividi il tempo in turni di n+1 unità. Nessuna lettera può essere eseguita due volte in un turno, e una lettera in una certa posizione di un turno può essere eseguita di nuovo nella stessa posizione del turno successivo, esattamente n+1 unità dopo. In ogni turno, esegui le lettere di cui restano più copie. Le loro esecuzioni rimanenti devono restare distanziate di n+1, quindi sono quelle che possono imporre tempo inattivo alla fine; eseguirle per prime mantiene i conteggi bilanciati.

Un turno che lascia del lavoro in sospeso dura n+1 unità, con gli slot vuoti inattivi; l’ultimo turno dura solo quanto le attività eseguite. Nell’esempio 1 i turni eseguono C A B, poi C A e un’unità inattiva, quindi l’ultimo C: 3 + 3 + 1 = 7. Ogni estrazione esegue un’attività, quindi con m attività e k ≤ 26 lettere, la complessità è O(m log k).

Algoritmo

Conta ogni lettera e inserisci in un max-heap i conteggi maggiori di zero.
Finché l'heap non è vuoto, esegui un turno: estrai fino a n+1 conteggi e conserva ciascun conteggio diminuito di uno, se è ancora maggiore di zero.
Reinserisci i conteggi conservati.
Aggiungi n+1 al tempo se l'heap non è vuoto; altrimenti aggiungi il numero di attività eseguite nel turno.
Restituisci il tempo.

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

Conta i fotogrammi della lettera più frequente

Intuizione

Sia top il conteggio più alto, raggiunto dalla lettera X. Disponi X lasciando n slot liberi dopo ogni sequenza, tranne l’ultima: top-1 intervalli di n+1 unità, poi l’ultima sequenza di X. Una lettera con meno di top copie entra negli slot liberi, una copia per intervallo, così le sue copie restano distanti almeno n+1 unità. Ogni altra lettera con top copie aggiunge un’unità alla fine. Con atTop lettere che hanno il conteggio massimo, si ottengono (top-1) × (n+1) + atTop unità.

Nessuna pianificazione è più breve: dividi le prime (top-1) × (n+1) unità in top-1 finestre di n+1. Ogni lettera con conteggio massimo compare al massimo una volta per finestra, quindi tutte e atTop hanno ancora una sequenza da eseguire dopo le finestre. Se ci sono più attività che slot liberi, lascia che alcuni intervalli superino n+1. Un intervallo più lungo allarga soltanto gli spazi, quindi non ci sono unità inattive e la risposta è m. La risposta è il maggiore dei due valori.

Algoritmo

Conta ciascuna delle 26 lettere.
Trova top, il conteggio più alto, e atTop, quante lettere lo hanno.
Calcola frames = (top-1) × (n+1) + atTop.
Restituisci il maggiore tra frames e il numero di attività.

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

Trappole e casi limite

Dimenticare le lettere a pari merito in cima. In "MMNNPP" con n = 5 tutte e tre le lettere hanno conteggio 2, quindi la risposta è (2-1) × 6 + 3 = 9, non 7.
Dimenticare il passaggio del massimo. Nell'esempio 2, i frame danno (2-1) × 2 + 2 = 4, ma sei attività richiedono sei unità.
Addebitare all'ultimo round n+1 unità intere. Dopo l'ultima attività non c'è nulla in attesa: l'esempio 3 darebbe 12 invece di 9.
Rimettere un conteggio all'interno del round. La stessa lettera può quindi essere estratta di nuovo in quel round ed essere eseguita due volte a distanza troppo ravvicinata.

Domande frequenti3

Qual è la complessità temporale di Task Scheduler?

Contare le lettere richiede O(m) per m attività, e poi la formula legge 26 conteggi, quindi la soluzione richiede O(m) tempo e O(1) memoria aggiuntiva. La simulazione con max-heap esegue un'estrazione per attività: O(m log k) con k ≤ 26 lettere.

Quando Task Scheduler non richiede tempo di inattività?

Quando m ≥ (top-1) × (n+1) + atTop, le attività riempiono ogni slot libero e allungano i frame invece di lasciare spazi vuoti, quindi la risposta è m. L’esempio 2, "ABCABD" con n = 1, è un caso del genere.

L'ordine della stringa di input è importante?

No. Scegli l’ordine in cui il processore esegue le attività, quindi conta solo quante volte compare ciascuna lettera. "CACBAC" e "CCCAAB" con n = 2 richiedono entrambi 7 unità.

def leastInterval(tasks, n):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

tasks = "CACBAC"
n = 2

Output atteso