Retour à la série « Stratégies »Exercice 8 sur 10
Physique • 10e HarmoS • Stratégies
Réf: phys-10h-strat-008Énoncé de l'exercice 8
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) :
- 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 ?
- 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
- Seulement ateliers () ; 2. ateliers au maximum : .
Corrigé détaillé et méthode étape par étape
Développement pédagogique complet conforme aux exigences HarmoS.
-
Stratégie naïve (« commence le plus tôt ») : On prend (), qui bloque . Il ne reste après que () et (), soit ateliers (). (De même, prendre l'atelier le plus court de à bloque et , ne permettant aussi que ateliers au total.)
-
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, finit le plus tôt ().
- À partir de , commence trop tôt () ; parmi , c'est () qui finit le plus tôt ().
- À partir de , commence trop tôt () ; on choisit (), puis ().
On case ainsi ateliers (), ce qui est le maximum possible (au plus avant et après ).