Dérouler la sélection d'activités

Algorithmes gloutons · niveau 1 (application)

Énoncé

Soient sept activités : $A (8, 10)$ , $B (9, 12)$ , $C (11, 13)$ , $D (12, 14)$ , $E (8, 9)$ , $G (9, 11)$ , $F (13, 16)$ (où chaque couple représente le début et la fin). Dérouler l'algorithme glouton par date de fin croissante.

Corrigé

Tri des activités par date de fin croissante : $E (8, 9), A (8, 10), G (9, 11), B (9, 12), C (11, 13), D (12, 14), F (13, 16)$ .
Parcours glouton :

Choisir $E (8, 9)$ (fin courante = $9$ ).
$A (8, 10)$ est rejetée car début $8 < 9$ .
Choisir $G (9, 11)$ car début $9 \geq 9$ (fin courante = $11$ ).
$B (9, 12)$ est rejetée car début $9 < 11$ .
Choisir $C (11, 13)$ car début $11 \geq 11$ (fin courante = $13$ ).
$D (12, 14)$ est rejetée car début $12 < 13$ .
Choisir $F (13, 16)$ car début $13 \geq 13$ (fin courante = $16$ ). Le cardinal maximal est de $4$ activités, et la sélection finale est ${E (8, 9), G (9, 11), C (11, 13), F (13, 16)}$ .

Énoncé

Corrigé

Exercices semblables