Task Scheduler

Q: Quelle est la complexité temporelle de Task Scheduler ?

Compter les lettres prend O(m) pour m tâches, et la formule lit ensuite 26 compteurs ; la solution a donc une complexité temporelle de O(m) et utilise O(1) mémoire supplémentaire. La simulation avec un tas max effectue une extraction par tâche, soit O(m log k) avec k ≤ 26 lettres.

Q: Quand le Planificateur de tâches n’a-t-il pas besoin de temps d’inactivité ?

Lorsque m ≥ (top-1) × (n+1) + atTop , les tâches remplissent tous les créneaux disponibles et étirent les intervalles au lieu de laisser des espaces vides, donc la réponse est m . L’exemple 2, "ABCABD" avec n = 1 , est un tel cas.

MoyenGlouton Tas Hachage

+10

On vous donne une chaîne tasks composée de lettres majuscules, une lettre par tâche, ainsi qu’un entier n. Un processeur exécute une tâche par unité de temps, dans l’ordre de votre choix, ou reste inactif pendant une unité.

Deux exécutions de la même lettre doivent être séparées d’au moins n unités : une lettre exécutée à l’unité t peut être exécutée de nouveau au plus tôt à l’unité t+n+1. Renvoyez le nombre minimal d’unités nécessaires pour exécuter toutes les tâches.

Fonction

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

tasksstring: les tâches, une lettre majuscule chacune
ninteger: le plus petit nombre d’unités entre deux séquences de la même lettre
Renvoieinteger: le plus petit nombre d’unités, y compris les unités inactives

Contraintes

1 ≤ tasks.length ≤ 10⁴
tasks ne contient que les lettres majuscules A à Z.
0 ≤ n ≤ 100

Exemples

Entrée: tasks = "CACBAC"n = 2
Sortie: 7
Explication: C s’exécute trois fois avec deux unités entre chaque exécution, donc ses seules exécutions s’étendent sur 7 unités. L’ordre C A B C A, une unité d’inactivité, C comble les intervalles avec A et B et nécessite une unité d’inactivité : 7.

Entrée: tasks = "ABCABD"n = 1
Sortie: 6
Explication: A et B s’exécutent chacun deux fois, avec une unité entre les exécutions. L’ordre A B C A B D les maintient séparés sans unité inactive, donc la réponse est le nombre de tâches, 6.

Entrée: tasks = "ZZZ"n = 3
Sortie: 9
Explication: Seul Z est exécuté, donc chaque intervalle est inactif : Z, trois unités inactives, Z, trois unités inactives, Z. Cela fait 9 unités.

Pour aller plus loin

Peux-tu également renvoyer un ordonnancement de longueur minimale, sous forme de chaîne avec un . pour chaque unité d’inactivité ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Tu choisis l’ordre, donc la question est de savoir combien d’unités d’inactivité au minimum sont nécessaires. La lettre la plus fréquente détermine tout : ses occurrences doivent être espacées de n+1 unités, et les autres tâches remplissent les intervalles entre elles. Traite d’abord les lettres les plus fréquentes à l’aide d’un tas max, ou compte directement les intervalles à l’aide d’une seule formule.

Simuler des manches avec un tas max

Intuition

Découpez le temps en périodes de n+1 unités. Aucune lettre ne peut être exécutée deux fois dans une période, et une lettre exécutée à un emplacement donné d’une période peut l’être à nouveau au même emplacement de la période suivante, exactement n+1 unités plus tard. Dans chaque période, exécutez les lettres qui ont le plus d’occurrences restantes. Leurs exécutions restantes doivent rester espacées de n+1 unités : ce sont donc elles qui peuvent imposer des temps d’inactivité à la fin. Les exécuter en premier permet de garder les comptes à niveau.

Une période qui laisse du travail à faire coûte n+1 unités, ses emplacements vides étant des temps d’inactivité ; la dernière période ne coûte que le nombre de tâches qu’elle exécute. Dans l’exemple 1, les périodes exécutent C A B, puis C A et une unité d’inactivité, puis le dernier C : 3 + 3 + 1 = 7. Chaque extraction exécute une tâche ; avec m tâches et k ≤ 26 lettres, la complexité est donc O(m log k).

Algorithme

Comptez chaque lettre et placez les nombres d’occurrences supérieurs à zéro dans un tas max.
Tant que le tas n’est pas vide, effectuez un tour : retirez jusqu’à n+1 nombres d’occurrences et conservez chaque nombre diminué de un s’il est toujours supérieur à zéro.
Réinsérez les nombres conservés.
Ajoutez n+1 au temps si le tas n’est pas vide ; sinon, ajoutez le nombre de tâches effectuées pendant le tour.
Retournez le temps.

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

Compter les occurrences de la lettre la plus fréquente

Intuition

Soit top le nombre maximal, détenu par la lettre X. Disposons les X en laissant n emplacements libres après chaque série, sauf la dernière : top-1 blocs de n+1 unités, puis la dernière série de X. Une lettre présente moins de top fois tient dans les emplacements libres, à raison d’une occurrence par bloc, de sorte que ses occurrences restent espacées d’au moins n+1 unités. Chaque autre lettre présente top fois ajoute une unité à la fin. Avec atTop lettres ayant le nombre maximal d’occurrences, cela fait (top-1) × (n+1) + atTop unités.

Aucun ordonnancement ne peut être plus court : découpons les (top-1) × (n+1) premières unités en top-1 fenêtres de n+1. Chaque lettre ayant le nombre maximal d’occurrences apparaît au plus une fois par fenêtre ; les atTop lettres ont donc encore chacune une occurrence après ces fenêtres. S’il y a plus de tâches que d’emplacements libres, laissons certaines périodes dépasser n+1. Une période plus longue ne fait qu’élargir les intervalles, donc aucune période n’est inactive et la réponse est m. La réponse est la plus grande des deux valeurs.

Algorithme

Compte chacune des 26 lettres.
Trouve top, le nombre le plus élevé, et atTop, le nombre de lettres qui l’atteignent.
Calcule frames = (top-1) × (n+1) + atTop.
Retourne la plus grande valeur entre frames et le nombre de tâches.

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

Pièges et cas limites

Oublier les lettres à égalité en tête. Dans "MMNNPP" avec n = 5, les trois lettres ont toutes un compte de 2, donc la réponse est (2-1) × 6 + 3 = 9, et non 7.
Oublier l’étape consistant à prendre la plus grande valeur. Dans l’exemple 2, les créneaux donnent (2-1) × 2 + 2 = 4, mais six tâches nécessitent six unités.
Compter une unité complète de n+1 pour le dernier tour. Rien n’attend après la dernière tâche : l’exemple 3 donnerait 12 au lieu de 9.
Remettre un compte dans le tour en cours. La même lettre peut alors être extraite à nouveau pendant ce tour et exécutée deux fois à trop peu d’intervalle.

Questions fréquentes3

Quelle est la complexité temporelle de Task Scheduler ?

Compter les lettres prend O(m) pour m tâches, et la formule lit ensuite 26 compteurs ; la solution a donc une complexité temporelle de O(m) et utilise O(1) mémoire supplémentaire. La simulation avec un tas max effectue une extraction par tâche, soit O(m log k) avec k ≤ 26 lettres.

Quand le Planificateur de tâches n’a-t-il pas besoin de temps d’inactivité ?

Lorsque m ≥ (top-1) × (n+1) + atTop, les tâches remplissent tous les créneaux disponibles et étirent les intervalles au lieu de laisser des espaces vides, donc la réponse est m. L’exemple 2, "ABCABD" avec n = 1, est un tel cas.

L’ordre de la chaîne d’entrée a-t-il de l’importance ?

Non. Tu choisis l’ordre dans lequel le processeur exécute les tâches, donc seul le nombre d’occurrences de chaque lettre compte. "CACBAC" et "CCCAAB" avec n = 2 nécessitent tous deux 7 unités.

def leastInterval(tasks, n):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

tasks = "CACBAC"
n = 2

Résultat attendu