Activity Selection Problem

Q: Quelle est la complexité temporelle du problème de sélection d’activités ?

Le tri par heure de fin coûte O(n log n) , et le parcours glouton qui suit coûte O(n) ; le tri est donc l’étape dominante. Si les activités sont déjà triées par heure de fin, le parcours seul suffit à résoudre le problème en O(n) temps et avec O(1) espace supplémentaire.

FacileGlouton Tri

+10

L’activité i se déroule de l’heure start[i] à l’heure finish[i]. Une personne ne fait qu’une activité à la fois, et l’activité suivante doit commencer strictement après la fin de la précédente : une activité qui commence exactement au moment où une autre se termine ne peut pas la suivre.

Renvoie le nombre maximal d’activités qu’une personne peut faire.

Fonction

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: l'heure de début de chaque activité
finishinteger-array: l'heure de fin de chaque activité ; finish[i] correspond à start[i]
Renvoieinteger: le plus grand nombre d’activités qu’une personne peut faire, l’une après l’autre

Contraintes

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
Une activité peut commencer et se terminer en même temps. Les tableaux ne sont pas triés.

Exemples

Entrée: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Sortie: 4
Explication: Faire 10 à 13, 14 à 19, 21 à 22 et 25 à 30 donne 4. Cinq est impossible : 10 à 13 entre en conflit avec 12 à 16, et 21 à 22 avec 20 à 24.

Entrée: start = [1, 5, 9]finish = [5, 9, 12]
Sortie: 2
Explication: L’activité de 5 à 9 commence exactement au moment où la première se termine, elle ne peut donc pas la suivre. Faire celle de 1 à 5 puis celle de 9 à 12 fonctionne, la réponse est donc 2.

Entrée: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Sortie: 3
Explication: L’activité de 0 à 100 chevauche toutes les autres. En la laissant de côté, 2 à 4, 5 à 7 et 8 à 10 s’enchaînent : 3.

Pour aller plus loin

Deux personnes travaillent maintenant en parallèle, chacune en réalisant une activité à la fois. Combien d’activités peuvent-elles réaliser ensemble, et laquelle chacune devrait-elle prendre en charge ?

Solution

Essayer tous les sous-ensembles d’activités prend un temps exponentiel. Une seule règle gloutonne suffit à trancher la question : parmi les activités qui peuvent encore être planifiées, choisissez toujours celle qui se termine en premier. Le tri par heure de fin permet d’appliquer cette règle en un seul passage.

Choisissez la fin la plus précoce, encore et encore

Correcte, mais ne termine pas sur les plus gros tests

Intuition

L’activité qui se termine le plus tôt est au moins aussi bon premier choix que n’importe quelle autre. Elle ne te libère pas plus tard, donc toute activité qui pourrait suivre un autre premier choix peut aussi la suivre, et la remplacer permet de conserver le nombre. Après ce choix, le problème se répète avec les activités qui commencent après sa fin.

Dans le premier exemple, tu choisis 10 à 13, puis 14 à 19, puis 21 à 22, puis 25 à 30 : quatre.

Chaque choix parcourt les n activités, donc le coût est égal à n fois la réponse. Lorsque les 5000 activités peuvent s’enchaîner, cela représente 25 millions de vérifications.

Algorithme

Définis count = 0 et lastFinish = -1, en dessous de chaque début.
Parcours toutes les activités pour trouver celle dont start[i] > lastFinish et qui se termine en premier.
S’il n’y en a aucune, retourne count.
Sinon, ajoute 1 à count, définis lastFinish comme la fin de cette activité, puis parcours à nouveau.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Trier par heure de fin et sélectionner de manière gloutonne

Intuition

Triez une fois par heure de fin, et vous rencontrerez les activités dans l’ordre où les parcours ci-dessus les ont recherchées. Parcourez la liste triée en gardant lastFinish, l’heure de fin de la dernière activité que vous avez choisie. Une activité avec start[i] > lastFinish est celle qui se termine le plus tôt parmi celles qui conviennent encore, alors choisissez-la. Toute autre activité entre en conflit avec votre dernier choix, donc l’ignorer ne coûte rien.

Une fois trié, le premier exemple donne 10 à 13, 12 à 16, 14 à 19, 21 à 22, 20 à 24, 25 à 30. Vous choisissez la première, la troisième, la quatrième et la sixième : 12 n’est pas après 13, et 20 n’est pas après 22.

Il n’y a pas besoin de règle pour les heures de fin identiques. Une fois que vous choisissez une activité qui se termine à t, toutes les autres qui se terminent à t commencent à t ou avant et sont ignorées.

Algorithme

Triez les activités par finish, en déplaçant chaque heure de début avec son heure de fin.
Définissez count = 0 et lastFinish = -1.
Pour chaque activité dans cet ordre, si start[i] > lastFinish, ajoutez 1 à count et définissez lastFinish = finish[i].
Renvoyez count.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

Pièges et cas limites

Le tri par heure de début. Dans le troisième exemple, l’activité de 0 à 100 commence en premier et bloque les trois autres.
Choisir d’abord l’activité la plus courte. Avec les activités de 1 à 5, de 5 à 6 et de 6 à 10, la plus courte est celle de 5 à 6, qui chevauche les deux autres ; celles de 1 à 5 et de 6 à 10 permettent d’en choisir 2.
Comparer avec ≥ au lieu de >. Dans le deuxième exemple, cela renvoie 3 au lieu de 2.
Trier finish séparément. Chaque heure de début doit rester associée à sa propre heure de fin, sinon les heures de début sont associées aux mauvaises activités.
Initialiser lastFinish à 0. Une activité isolée de 0 à 1 est alors ignorée, car 0 > 0 est faux.

Questions fréquentes3

Quelle est la complexité temporelle du problème de sélection d’activités ?

Le tri par heure de fin coûte O(n log n), et le parcours glouton qui suit coûte O(n) ; le tri est donc l’étape dominante. Si les activités sont déjà triées par heure de fin, le parcours seul suffit à résoudre le problème en O(n) temps et avec O(1) espace supplémentaire.

Quel est le problème des N réunions dans une même salle ?

C’est le même problème présenté avec des réunions : une salle, N réunions, et une réunion ne peut commencer qu’après la fin de la précédente. Trie les réunions par heure de fin et prends chacune de celles qui commencent après la fin de la dernière réunion prise. Pour lister les réunions, note chaque indice que tu prends, en départageant les réunions ayant la même heure de fin par l’indice le plus petit.

Le problème de sélection d’activités relève-t-il de la programmation dynamique ?

C’est possible, mais ce n’est pas nécessaire. Un tableau des activités triées par heure de fin, qui indique le nombre maximal d’activités se terminant par chacune d’elles, donne la réponse en O(n²). Le choix glouton est toujours sûr, donc un seul parcours suffit. Le tableau devient l’outil adapté lorsque les activités ont des valeurs et que tu cherches à maximiser leur total.

def maxActivities(start, finish):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

Résultat attendu