Planificateur de tâches et station-service

Ordonnanceur de tâches (LeetCode 621) : étant donné une liste de tâches du CPU, chacune étiquetée de A à Z, ainsi qu’un délai de refroidissement n, trouvez le nombre minimal d’intervalles du CPU nécessaires pour terminer toutes les tâches. Une même tâche doit attendre au moins n intervalles avant d’être exécutée de nouveau. Les intervalles d’inactivité sont autorisés. Pour les tâches ['A','A','A','B','B','B'] avec un délai de refroidissement de 2, la réponse est 8 : A→B→idle→A→B→idle→A→B.

Idée clé : la durée totale est déterminée par la tâche la plus fréquente. Si la tâche la plus fréquente apparaît f fois et si max_count représente le nombre de tâches ayant cette fréquence f, la durée est max(len(tasks), (f-1) * (n+1) + max_count). La formule consiste à créer f-1 blocs de taille n+1, à les remplir avec les autres tâches, puis à ajouter le dernier cycle. Si les autres tâches remplissent tous les créneaux d’inactivité, notamment lorsqu’il existe de nombreuses tâches différentes, exécutez simplement toutes les tâches sans temps d’inactivité.

Imaginez l’ordonnancement comme une grille de n+1 colonnes, comprenant un créneau de tâche et n créneaux de refroidissement. La tâche A, qui est la plus fréquente, avec une fréquence f, nécessite f lignes. Entre la première et la dernière occurrence, il y a f-1 blocs complets de n+1 créneaux. Il faut ensuite ajouter le dernier bloc partiel, qui contient toutes les tâches ayant la fréquence maximale. S’il y a suffisamment de tâches différentes, elles remplissent tous les créneaux d’inactivité, et le nombre réel de tâches dépasse la durée des blocs — choisissez la plus grande des deux valeurs.

Une simulation fondée sur un tas produit l’ordonnancement réel, et pas seulement le nombre total. À chaque étape, prenez la tâche disponible la plus fréquente, à l’aide d’un tas-max. Après son exécution, appliquez le délai de refroidissement : ne la réinsérez qu’après n étapes. Utilisez une file pour suivre les tâches en cours de refroidissement. Cette solution s’exécute en O(total_time × log k), où k est le nombre de tâches distinctes. Bien qu’elle soit correcte, la formule est plus rapide. Connaissez les deux approches : les examinateurs peuvent vous demander de produire l’ordonnancement lui-même.

Station-service (LeetCode 134) : il y a n stations-service disposées en cercle. La station i possède gas[i] unités de carburant, et le trajet jusqu’à la station suivante coûte cost[i] unités. En partant avec un réservoir vide, trouvez la station de départ depuis laquelle vous pouvez effectuer le circuit complet. Si aucune station ne convient, renvoyez -1. Le problème garantit qu’il existe au plus une réponse valide lorsqu’une telle réponse existe.

Algorithme glouton : (1) Si le carburant total est inférieur au coût total, aucune solution n’existe (renvoyez -1). (2) Sinon, il existe exactement une solution. Trouvez-la en un seul parcours : suivez tank (le carburant actuel) et start (la station de départ candidate). Si tank < 0 après avoir visité une station, la station de départ actuelle ne peut pas atteindre cette station — réinitialisez tank = 0 et définissez start = i + 1. Le start final est la réponse.

Argument de correction : si le réservoir devient négatif après avoir atteint la station i depuis start, aucune station située entre start et i, bornes comprises, ne peut être un point de départ valide — à leur arrivée à la station i, elles disposent toutes de moins de carburant que celui dont disposerait un départ depuis start. Nous pouvons donc ignorer toutes ces stations en toute sécurité et essayer i+1. Puisqu’une solution existe, car le carburant total est supérieur ou égal au coût total, la dernière station candidate start doit fonctionner.

La force brute essaie chaque station de départ et simule le circuit complet — O(n²) en temps. La solution gloutonne en un seul parcours est en O(n) en temps et O(1) en espace. Pour un tableau de 10⁵ stations, la différence est de 10¹⁰ opérations contre 10⁵. La propriété mathématique clé qui permet l’approche gloutonne est la suivante : si le carburant net total est non négatif, un départ valide existe, et il s’agit toujours de la station située juste après le dernier point où la somme cumulée est devenue négative.

Temps minimal pour terminer les trajets (LeetCode 2187) est un problème de recherche binaire dans l’espace des réponses. Vous effectuez une recherche binaire sur la valeur du temps T : pour un temps T donné, les bus dont le temps est time[i] terminent floor(T/time[i]) trajets. Si le nombre total de trajets est ≥ totalTrips, T est suffisant. Il faut trouver le plus petit T répondant à cette condition. Cela montre que l’approche gloutonne peut s’appliquer au méta-niveau — en effectuant une recherche binaire parmi les réponses — lorsqu’aucune règle gloutonne directe n’existe au niveau des objets.

Cas limites importants pour les deux problèmes : Planificateur de tâches — lorsque le temps de refroidissement n=0, la réponse est simplement le nombre de tâches (aucune période d’inactivité n’est nécessaire). Lorsque toutes les tâches sont identiques, par exemple toutes « A », les périodes d’inactivité sont remplies exactement. Lorsque les tâches comportent de nombreux types distincts, le nombre de périodes d’inactivité peut être nul, car les tâches remplissent tous les créneaux. Station-service — lorsque la quantité totale de carburant est exactement égale au coût total, il existe une unique position de départ valide. Lorsqu’une seule station fournit suffisamment de carburant pour parcourir tout le circuit, cette station est la réponse. Vérifiez toujours votre réponse gloutonne sur ces cas dégénérés.

Le Planificateur de tâches et la Station-service suivent tous deux le schéma glouton suivant : (1) identifier le goulot d’étranglement, c’est-à-dire la tâche la plus fréquente ou le bilan net de carburant ; (2) prendre une décision en un seul parcours à l’aide d’une variable mise à jour au fil du parcours, comme la fréquence maximale ou le contenu du réservoir ; (3) recommencer ou réinitialiser lorsqu’une contrainte est enfreinte. Problèmes gloutons courants à connaître : sélection d’activités, codage de Huffman, problème du sac à dos fractionnaire, jeu de sauts, Planificateur de tâches, Station-service et fusion d’intervalles. Chacun possède une preuve par argument d’échange ou par invariant mathématique.

Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.

Dans cette leçon, vous avez appris que la réponse du Planificateur de tâches = maximum(nombre total de tâches, (fréquence maximale-1)*(n+1)+nombre maximal) — une formule obtenue en remplissant des grilles de créneaux à partir de la tâche la plus fréquente, que la Station-service s’exécute en un seul parcours et réinitialise le départ à i+1 chaque fois que le réservoir devient négatif ; une solution existe lorsque le carburant total ≥ le coût total, et que les deux problèmes utilisent un temps O(n) et un espace O(1) en identifiant un invariant mathématique plutôt qu’en effectuant une recherche exhaustive. Nous allons maintenant étudier le modèle diviser pour régner et ses applications au-delà du tri par fusion.