Job Sequencing Problem

Q: Quelle est la complexité temporelle du problème d’ordonnancement des tâches ?

Avec un ensemble disjoint, le temps d’exécution est de O(n log n) , dominé par le tri, et l’espace requis est de O(n) . Remonter à partir de chaque échéance pour trouver un créneau libre coûte O(n²) lorsque la plupart des échéances sont éloignées.

MoyenGlouton Tri

+10

Vous disposez de n tâches représentées par deux tableaux : la tâche i rapporte profit[i] si elle se termine au plus tard à deadline[i]. Chaque tâche prend une unité de temps, vous exécutez une tâche à la fois à partir du temps 0 et vous pouvez ignorer n’importe quelle tâche. Une tâche avec une échéance de 2 peut être exécutée de 0 à 1 ou de 1 à 2.

Renvoyez le profit total maximal que vous pouvez obtenir.

Fonction

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: le délai auquel chaque tâche doit être terminée, de 1 à n
profitinteger-array: ce que rapporte chaque tâche ; profit[i] correspond à deadline[i]
Renvoieinteger: le profit total maximal des tâches qui peuvent toutes se terminer avant leurs échéances

Contraintes

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, où n est le nombre de tâches
1 ≤ profit[i] ≤ 10⁵
Les tableaux ne sont pas triés. Plusieurs tâches peuvent avoir la même échéance ou le même profit.

Exemples

Entrée: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Sortie: 120
Explication: Un seul des deux travaux ayant une échéance de 1 peut être effectué, alors effectuez celui qui vaut 50. Le travail qui vaut 30 se termine ensuite à son échéance de 2 et celui qui vaut 40 à son échéance de 3 : 50 + 30 + 40 = 120.

Entrée: deadline = [1, 1, 1]profit = [5, 9, 7]
Sortie: 9
Explication: Les trois tâches doivent être terminées avant le temps 1, et une seule peut être effectuée d’ici là. La meilleure rapporte 9.

Pour aller plus loin

Et si la tâche i prenait duration[i] unités de temps au lieu d’une seule ? Commencer par la tâche la plus rentable donne-t-il toujours le meilleur total ?

Solution

Tu choisis quels travaux conserver et quand les exécuter. Une règle gloutonne règle les deux : prends les travaux du plus rentable au moins rentable et place chacun dans le créneau libre le plus tardif à sa date limite ou avant, en l’ignorant si aucun créneau n’est libre. Un ensemble disjoint trouve ce créneau sans parcourir les créneaux déjà occupés.

Glouton par profit, en recherchant un créneau libre

Intuition

Découpez le temps en créneaux : le créneau t va de t-1 à t, un travail dont l’échéance est d peut utiliser les créneaux 1 à d, et aucune échéance ne dépasse n. Prendre d’abord le travail le plus rentable est sans risque : si tous les créneaux qu’il pourrait utiliser sont occupés, l’échanger contre le travail dans l’un de ces créneaux rapporte au moins autant. Réserver le créneau le plus tardif est sans risque, car seuls les créneaux précoces sont accessibles aux travaux à échéance rapprochée.

Le coût vient du balayage. Lorsque chaque échéance vaut n, le k-ième travail passe devant k-1 créneaux occupés : environ n²/2, soit 12,5 millions d’étapes pour n = 5000.

Algorithme

Triez les tâches par profit décroissant, en gardant chaque échéance avec son profit.
Créez un tableau taken de n + 1 indicateurs, tous à false.
Pour chaque tâche, parcourez t à rebours depuis son échéance jusqu’à 1 et arrêtez-vous au premier créneau qui n’est pas pris.
Si vous en avez trouvé un, marquez-le comme pris et ajoutez le profit de la tâche à total.
Renvoyez total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Glouton par profit avec un ensemble disjoint de créneaux libres

Intuition

Le parcours repasse sans cesse sur les mêmes créneaux réservés. Une structure de données union-find sur les créneaux de 0 à n permet de les ignorer : parent[t] = t tant que le créneau t est libre, et sa réservation définit parent[t] = t-1, de sorte qu’en suivant les pointeurs depuis une échéance, on atteint le dernier créneau libre. Atteindre le créneau 0 signifie qu’il n’en reste aucun. La compression de chemin par division par deux fait pointer chaque créneau parcouru deux étapes plus loin, ce qui raccourcit les parcours suivants.

Dans le troisième exemple, les tâches valant 60 et 50 réservent les créneaux 2 et 1. La tâche valant 20, avec une échéance de 2, suit le chemin 2 vers 1, puis vers 0, et est ignorée.

Le tri coûte O(n log n), et avec la compression de chemin par division par deux, chaque recherche coûte O(log n) en coût amorti ; le coût total reste donc O(n log n).

Algorithme

Triez les tâches par profit décroissant, en conservant chaque échéance avec son profit.
Définissez parent[t] = t pour chaque créneau t de 0 à n.
Pour chaque tâche, commencez à slot = deadline et suivez parent jusqu’à ce que parent[slot] == slot, en divisant le chemin par deux au fur et à mesure.
Si slot > 0, ajoutez le profit de la tâche et définissez parent[slot] = slot-1 ; sinon, ignorez la tâche.
Renvoyez le total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Pièges et cas limites

Placer un travail dans le premier créneau libre. Dans le troisième exemple, le travail valant 60 prendrait le créneau 1, et le travail valant 50 serait perdu : 80 au lieu de 110.
Prendre les travaux par ordre d’échéance. Avec les échéances [1, 1] et les profits [1, 100], le travail le moins rémunérateur prend le seul créneau et tu gagnes 1 au lieu de 100.
Dimensionner le tableau des créneaux à n au lieu de n + 1. Une échéance égale à n entraîne alors une lecture au-delà de la fin du tableau.
Trier les profits seuls. Chaque échéance doit rester associée à son profit.
Écrire l’étape de recherche avec de la récursion. Une chaîne passant par des milliers de créneaux réservés peut faire déborder la pile ; utilise une boucle.

Questions fréquentes3

Quelle est la complexité temporelle du problème d’ordonnancement des tâches ?

Avec un ensemble disjoint, le temps d’exécution est de O(n log n), dominé par le tri, et l’espace requis est de O(n). Remonter à partir de chaque échéance pour trouver un créneau libre coûte O(n²) lorsque la plupart des échéances sont éloignées.

Pourquoi l’approche gloutonne fonctionne-t-elle pour l’ordonnancement des tâches ?

Un certain meilleur planning contient le travail le plus rentable. S’il est omis et qu’un créneau avant son échéance est libre, l’ajouter rapporte davantage ; si tous ces créneaux sont occupés, le remplacer par ce travail rapporte au moins autant. Le raisonnement se répète pour les travaux restants.

Peut-on résoudre la planification des tâches avec un tas à la place ?

Oui. Triez les tâches par échéance et ajoutez chaque profit dans un tas min. Chaque fois que le tas contient plus de tâches que ne le permet l’échéance actuelle, retirez le profit le plus faible. À la fin, le tas contient le meilleur ensemble de tâches, et sa somme est la réponse, en O(n log n).

def jobSequencing(deadline, profit):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Résultat attendu