30 min de cours gratuit et sans engagement !

Obtenir un cours gratuit
Physique • 10e HarmoS • Stratégies

Énoncé de l'exercice 8

Réf: phys-10h-strat-008
Stratégie de réservation d'une salle (ordonnancement) : Sept groupes demandent à réserver l'unique salle de travaux pratiques pour la journée. Voici leurs créneaux horaires (un créneau choisi doit être pris en entier et deux créneaux ne peuvent pas se chevaucher) :
AtelierABCDEFGHoraire8h00–13h009h00–10h3010h15–11h1511h00–13h0012h45–15h1515h00–16h3016h30–18h00\begin{array}{|c|c|c|c|c|c|c|c|} \hline \text{Atelier} & A & B & C & D & E & F & G \\ \hline \text{Horaire} & 8\text{h}00\text{–}13\text{h}00 & 9\text{h}00\text{–}10\text{h}30 & 10\text{h}15\text{–}11\text{h}15 & 11\text{h}00\text{–}13\text{h}00 & 12\text{h}45\text{–}15\text{h}15 & 15\text{h}00\text{–}16\text{h}30 & 16\text{h}30\text{–}18\text{h}00 \\ \hline \end{array}
  1. Quel nombre d'ateliers obtient-on si l'on applique la stratégie naïve consistant à choisir toujours l'atelier disponible qui commence le plus tôt ?
  2. Montrer qu'en choisissant à chaque étape l'atelier compatible qui se termine le plus tôt, on parvient à caser un nombre maximal d'ateliers (préciser lesquels).

Réponse finale

  1. Seulement 33 ateliers (A,F,GA, F, G) ; 2. 44 ateliers au maximum : B,D,F,GB, D, F, G.

Corrigé détaillé et méthode étape par étape

Développement pédagogique complet conforme aux exigences HarmoS.

  1. Stratégie naïve (« commence le plus tôt ») : On prend AA (8h00–13h008\text{h}00\text{–}13\text{h}00), qui bloque B,C,D,EB, C, D, E. Il ne reste après 13h0013\text{h}00 que FF (15h00–16h3015\text{h}00\text{–}16\text{h}30) et GG (16h30–18h0016\text{h}30\text{–}18\text{h}00), soit 33 ateliers (A,F,GA, F, G). (De même, prendre l'atelier le plus court CC de 10h1510\text{h}15 à 11h1511\text{h}15 bloque BB et DD, ne permettant aussi que 33 ateliers au total.)
  2. Stratégie gloutonne optimale (« finit le plus tôt ») : Pour libérer la salle au plus vite, on choisit toujours l'atelier compatible dont l'heure de fin est minimale :
  • Parmi tous les ateliers, BB finit le plus tôt (10h3010\text{h}30).
  • À partir de 10h3010\text{h}30, CC commence trop tôt (10h1510\text{h}15) ; parmi D,E,F,GD, E, F, G, c'est DD (11h00–13h0011\text{h}00\text{–}13\text{h}00) qui finit le plus tôt (13h0013\text{h}00).
  • À partir de 13h0013\text{h}00, EE commence trop tôt (12h4512\text{h}45) ; on choisit FF (15h00–16h3015\text{h}00\text{–}16\text{h}30), puis GG (16h30–18h0016\text{h}30\text{–}18\text{h}00).
On case ainsi 44 ateliers (B,D,F,GB, D, F, G), ce qui est le maximum possible (au plus 22 avant 13h0013\text{h}00 et 22 après 13h0013\text{h}00).