CHAPITRE 5 : LA SALLE DU FOYER : CASER LE PLUS D'ACTIVITÉS

Nadège gère le foyer du quartier, à Bafoussam. Une seule salle, et beaucoup de monde qui la réclame. Son problème : satisfaire le plus grand nombre de groupes possible.

Les demandes de la journée

Activité	Début	Fin
Réunion des tontines	8 h	11 h
Cours de couture	9 h	10 h
Assemblée du quartier	10 h	13 h
Répétition chorale	11 h	12 h
Formation informatique	12 h	15 h
Match retransmis	13 h	14 h
Veillée	14 h	17 h

Deux activités ne peuvent pas se chevaucher. En revanche, l'une peut commencer à l'heure exacte où l'autre finit : on considère que le ménage se fait vite.

Attention à ce qu'on cherche : Nadège veut le plus grand nombre de groupes satisfaits, pas la salle occupée le plus longtemps. Ce n'est pas du tout le même problème, et nous y reviendrons.

Trois critères possibles

Face à ce problème, trois idées viennent naturellement :

Le premier arrivé : prendre les demandes par heure de début croissante ;
Le plus court : commencer par les activités les plus brèves, pour en caser davantage ;
Celui qui libère le plus tôt : prendre par heure de fin croissante.

Les trois sont des critères gloutons parfaitement légitimes. Un seul est correct.

Le critère qui gagne

Trier par heure de fin croissante, puis prendre toute activité qui commence après la fin de la précédente.

Déroulons :

trie par heure de fin :
   Cours de couture        9h - 10h
   Reunion des tontines    8h - 11h
   Repetition chorale     11h - 12h
   Assemblee du quartier  10h - 13h
   Match retransmis       13h - 14h
   Formation informatique 12h - 15h
   Veillee                14h - 17h

on parcourt :
   Cours de couture        9h-10h   -> PRIS   (salle libre a 10h)
   Reunion des tontines    debut 8h  < 10h    -> refuse
   Repetition chorale     11h-12h   -> PRIS   (salle libre a 12h)
   Assemblee du quartier  debut 10h < 12h     -> refuse
   Match retransmis       13h-14h   -> PRIS   (salle libre a 14h)
   Formation informatique debut 12h < 14h     -> refuse
   Veillee                14h-17h   -> PRIS

resultat : 4 activites

Quatre groupes satisfaits. Et la force brute confirme : quatre est le maximum.

Pourquoi les deux autres critères échouent

Le premier arrivé ne donne que trois activités sur notre journée. La réunion des tontines commence à 8 h et bloque la salle jusqu'à 11 h ; pendant ce temps, le cours de couture, qui n'aurait pris qu'une heure, est perdu.

Le plus court est plus subtil. Sur notre journée il donne aussi quatre activités : il a de la chance. Voici un cas où il s'effondre :

Activité	Horaire	Durée
Tontine des mamans	8 h – 13 h	5 h
Point rapide du chef	12 h – 14 h	2 h
Répétition chorale	13 h – 18 h	5 h

Le critère « le plus court » prend d'abord le point du chef. Mais ses deux heures mordent à la fois sur la tontine (qui finit à 13 h) et sur la chorale (qui commence à 13 h). Résultat : une seule activité.

Le critère « heure de fin » prend la tontine (finit à 13 h), puis la chorale (commence à 13 h) : deux activités, ce qui est l'optimum.

Une courte réunion mal placée coûte plus cher que deux longues bien rangées.

La démonstration

Affirmation. Trier par date de fin croissante donne toujours le nombre maximal d'activités compatibles.

Démonstration, par argument d'échange.

Soit G = (g₁, g₂, …, g_p) la solution du glouton, rangée par date de fin, et soit O = (o₁, o₂, …, o_q) une solution optimale, rangée de même. On veut montrer que p = q.

Premier pas. Par construction, g₁ est l'activité qui finit le plus tôt de toutes. Donc :

fin(g₁) ≤ fin(o₁)

On peut alors remplacer o₁ par g₁ dans O sans rien casser : g₁ finit au plus tard quand o₁ finissait, donc o₂, qui commençait après o₁, commence aussi après g₁. La solution obtenue a toujours q activités : elle est toujours optimale.

Récurrence. Une fois g₁ fixée, le problème restant est le même, posé sur les activités qui commencent après fin(g₁). Le glouton y choisit encore celle qui finit le plus tôt, et le même échange s'applique.

En répétant, on transforme O en une solution qui commence par g₁, g₂, …, g_p : toujours optimale, donc toujours de taille q.

Conclusion. Après avoir placé les p activités du glouton, peut-il rester des activités dans O ? Non : une telle activité commencerait après fin(g_p), et le glouton l'aurait donc prise, or il s'est arrêté. Donc q = p. ∎

Le code

def planifier(demandes):
    # demandes : liste de (nom, debut, fin). Renvoie le plus grand ensemble
    # d'activites compatibles
    par_fin = sorted(demandes, key=lambda d: d[2])

    retenues = []
    libre_a = 0                       # heure a laquelle la salle se libere

    for nom, debut, fin in par_fin:
        if debut >= libre_a:          # la salle est disponible
            retenues.append((nom, debut, fin))
            libre_a = fin

    return retenues

>>> for a in planifier(DEMANDES):
...     print("%2dh-%2dh  %s" % (a[1], a[2], a[0]))
 9h-10h  Cours de couture
11h-12h  Repetition chorale
13h-14h  Match retransmis
14h-17h  Veillee

Complexité : O(n log n), dominée par le tri. Le parcours lui-même est linéaire.

Le piège : changer l'objectif

Supposons maintenant que Nadège soit payée à l'heure d'occupation. Son objectif n'est plus de satisfaire le plus de groupes, mais de remplir la salle le plus longtemps possible.

Sur notre journée, le glouton par heure de fin donne 1 + 1 + 1 + 3 = 6 heures. Mais retenir la réunion des tontines (3 h), la répétition chorale (1 h), le match (1 h) et la veillée (3 h) remplirait 8 heures : avec le même nombre d'activités.

Changer l'objectif change le problème. Et ce problème-là, maximiser la durée, n'admet aucun glouton optimal : il est NP-difficile.

Même la stratégie qui paraît évidente, prendre les activités par durée décroissante, échoue. C'est un rappel utile : un glouton se démontre pour un objectif donné, jamais « en général ».

À retenir

Pour caser le plus d'activités : trier par heure de fin, jamais par début ni par durée.
L'intuition « commencer par les plus courtes » est fausse, et le contre-exemple est facile à construire.
La preuve se fait par échange : la première activité du glouton peut toujours remplacer celle d'une solution optimale.
Changer l'objectif, maximiser la durée au lieu du nombre, détruit l'optimalité.

Exercices d'application

Exercice 1

Appliquez le critère « heure de fin » aux demandes suivantes et donnez le résultat.
A : 9h–11h · B : 10h–12h · C : 11h–13h · D : 12h–14h · E : 13h–15h

Voir le corrigeMasquer le corrige

Les activités sont déjà triées par heure de fin.

salle libre a 0

A  9h-11h : 9 >= 0   -> PRIS     salle libre a 11h
B 10h-12h : 10 < 11  -> refuse
C 11h-13h : 11 >= 11 -> PRIS     salle libre a 13h
D 12h-14h : 12 < 13  -> refuse
E 13h-15h : 13 >= 13 -> PRIS     salle libre a 15h

resultat : A, C, E  ->  3 activites

C'est bien l'optimum : les cinq activités se chevauchent deux à deux en chaîne, et il est impossible d'en caser quatre.

Noter que A, C et E se succèdent exactement : la salle ne désemplit pas. Le glouton par heure de fin produit souvent ce genre d'enchaînement serré, et c'est précisément ce qui le rend optimal.

Exercice 2

Construisez un jeu de trois demandes où trier par heure de début donne un résultat strictement moins bon que trier par heure de fin.

Voir le corrigeMasquer le corrige

Il suffit qu'une activité très longue commence la première :

Activité	Horaire
Assemblée générale	8 h – 18 h
Cours d'alphabétisation	9 h – 11 h
Réunion du comité	12 h – 14 h

Par heure de début : on prend l'assemblée générale (8 h), qui occupe la salle jusqu'à 18 h. Les deux autres sont refusées. 1 activité.

Par heure de fin : on trie en cours (11 h), réunion (14 h), assemblée (18 h). On prend le cours, puis la réunion (12 ≥ 11), puis on refuse l'assemblée. 2 activités.

Le défaut du critère « premier arrivé » saute aux yeux : il ne regarde pas quand la salle se libère, qui est pourtant la seule information utile pour la suite.

Exercice 3

Nadège dispose maintenant de deux salles. Le glouton par heure de fin suffit-il ?

Voir le corrigeMasquer le corrige

Non, il ne suffit plus, et c'est un piège classique.

Avec une salle, le glouton maintient une seule information : l'heure à laquelle la salle se libère. Avec deux salles, il faudrait décider, pour chaque activité retenue, dans laquelle la placer, et ce choix engage la suite.

Exemple : A 8h–10h, B 9h–11h, C 10h–12h. Le glouton naïf prend A (salle 1), puis B (salle 2), puis C : qui commence à 10 h, donc après A. Il le met en salle 1. Trois activités, c'est correct ici.

Mais le problème général : répartir des activités sur k salles en maximisant le nombre total : demande un autre algorithme. Le problème voisin « combien de salles faut-il au minimum pour tout caser ? » se résout lui par un glouton différent : on trie par heure de début et on maintient une file à priorité des salles occupées. Le nombre de salles nécessaires est le nombre maximal d'activités simultanées.

Deux problèmes très proches, deux critères gloutons opposés. Il faut redémontrer à chaque fois.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.