Servir d'abord les demandes les plus courtes

Servir d'abord les demandes les plus courtes.

Quatre clients attendent devant un guichet unique. Leurs demandes durent respectivement $8$, $3$, $5$ et $1$ minutes. Le temps d'attente d'un client est la durée écoulée avant le début de son service.

• Calculer le temps d'attente total si l'on sert les clients dans l'ordre d'arrivée.
• Proposer un critère glouton pour minimiser le temps d'attente total, et calculer ce total.
• Écrire une fonction attente_totale(durees) et une fonction meilleur_ordre(durees).
• Justifier l'optimalité du critère par un argument d'échange.