Un bureau d'études lance chaque soir des calculs de simulation sur une grappe de serveurs. Chaque calcul occupe un serveur entier pendant son créneau, et un serveur ne traite qu'un calcul à la fois. Le planificateur actuel attribue les serveurs dans l'ordre où les calculs ont été soumis, et l'équipe se demande s'il n'allume pas une machine de trop.
La situation
Les huit calculs de ce soir, dans l'ordre de soumission. Un créneau commence à et libère le serveur à .
| Calcul | Début | Fin |
|---|---|---|
| T1 | 14 h | 17 h |
| T2 | 15 h | 19 h |
| T3 | 18 h | 22 h |
| T4 | 17 h | 20 h |
| T5 | 19 h | 23 h |
| T6 | 20 h | 21 h |
| T7 | 21 h | minuit |
| T8 | 16 h | 18 h |
Le planificateur applique l'algorithme glouton : il prend les calculs dans un ordre donné et affecte à chacun le serveur de plus petit numéro qu'aucun calcul en conflit, déjà placé, n'occupe.
Objectif
Construire le graphe des conflits et compter ses arêtes. Déterminer le nombre maximal de calculs simultanés. Compter les serveurs utilisés par le glouton dans l'ordre de soumission, puis dans l'ordre des heures de début croissantes, et conclure sur le nombre minimal de serveurs.