NSI (terminale) · Chapitre 8 · Exercice d'entraînement
Le nombre minimal de salles
Les algorithmes gloutons · Planifier et couvrir · niveau 2
Énoncé
Le nombre minimal de salles.
Un lycée doit accueillir des réunions dont on connaît l'heure de début et l'heure de fin. Deux réunions qui se chevauchent ne peuvent pas avoir lieu dans la même salle ; une réunion peut commencer dans une salle à l'heure exacte où une autre s'y termine. On veut utiliser le moins de salles possible.
reunions = [(9, 11), (9, 10), (10, 12), (11, 13), (12, 14), (10, 11), (13, 15)]- Quelle est l'heure de la journée où le plus de réunions ont lieu simultanément ? En déduire un minorant du nombre de salles.
- Stratégie gloutonne : on traite les réunions par heure de début croissante ; chacune est placée dans une salle déjà ouverte qui est libre à son heure de début, s'il y en a une, sinon on ouvre une nouvelle salle. Écrire une fonction
nb_salles(reunions)qui renvoie le nombre de salles utilisées. - Appliquer à l'exemple. La solution est-elle optimale ?
Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.