Combien de salles pour l'emploi du temps ?

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 7 — Algorithmes gloutons

Énoncé

En utilisant les sept activités de l'exercice précédent, dérouler l'algorithme d'allocation de salles et trouver un certificat d'optimalité.

Tri par début croissant : $A (8, 10), E (8, 9), B (9, 12), G (9, 11), C (11, 13), D (12, 14), F (13, 16)$ .
Affectation gloutonne :

$A (8, 10) \to$ Salle 1 (heure de fin de la Salle 1 = $10$ ).
$E (8, 9) \to$ Salle 2 (fin de Salle 2 = $9$ ).
$B (9, 12)$ : Salle 1 occupée ( $10 > 9$ ), Salle 2 libre ( $9 \leq 9$ ) $\to$ affectation à la Salle 2 (fin de Salle 2 = $12$ ).
$G (9, 11)$ : Salle 1 occupée ( $10 > 9$ ), Salle 2 occupée ( $12 > 9$ ) $\to$ ouverture de la Salle 3 (fin de Salle 3 = $11$ ).
$C (11, 13)$ : Salle 1 libre ( $10 \leq 11$ ) $\to$ affectation à la Salle 1 (fin de Salle 1 = $13$ ).
$D (12, 14)$ : Salle 1 occupée ( $13 > 12$ ), Salle 2 libre ( $12 \leq 12$ ) $\to$ affectation à la Salle 2 (fin de Salle 2 = $14$ ).
$F (13, 16)$ : Salle 1 libre ( $13 \leq 13$ ) $\to$ affectation à la Salle 1 (fin de Salle 1 = $16$ ). L'algorithme utilise au total $3$ salles. Certificat d'optimalité : À l'instant critique $t = 9.5$ , les activités $A (8, 10)$ , $B (9, 12)$ et $G (9, 11)$ sont simultanément en cours d'exécution. Elles imposent l'usage d'au moins 3 salles distinctes.

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.