Trier par durée ne suffit pas

Contre-exemple au tri par durée : $(9,12)$, $(11,13)$, $(12,15)$, de durées $3$, $2$, $3$.

Le tri par durée place $(11,13)$ en tête ; on le retient, la salle se libère à $13$. Ensuite $(9,12)$ commence à $9<13$ : refusé. Et $(12,15)$ commence à $12<13$ : refusé aussi. Un seul cours.

Le tri par heure de fin donne l'ordre $(9,12)$, $(11,13)$, $(12,15)$ : on retient $(9,12)$, la salle se libère à $12$ ; $(11,13)$ est refusé, mais $(12,15)$ commence à $12$ et passe. Deux cours.

Contre-exemple au tri par heure de début : $(9,17)$, $(10,12)$, $(13,15)$.

Le tri par début retient d'abord le cours-fleuve $(9,17)$, qui bloque la salle jusqu'au soir : les deux autres sont refusés. Un seul cours. Le tri par heure de fin retient $(10,12)$ puis $(13,15)$ : deux cours.

Pourquoi la fin est le bon critère. Retenir un cours a un seul coût pour la suite : l'heure à laquelle la salle redevient libre. Le critère qui optimise ce coût à chaque étape est donc l'heure de fin, et rien d'autre. La durée l'ignore, l'heure de début aussi.

Le point à retenir. Un glouton est entièrement défini par son critère de choix. Changer le critère ne le rend pas seulement plus lent : cela en fait un autre algorithme, ici incorrect. C'est la même leçon que le rendu de monnaie, prise par l'autre bout — là c'était le système qui décidait, ici c'est le critère.