Nombre minimal de quais
Un chef de gare a devant lui la liste des trains passant par sa gare dans la journée. Il lève les yeux vers les quais : aucun train n'est actuellement stationné. Il se demande alors combien de quais seront occupés au maximum à n'importe quel moment de la journée.
La liste des horaires des trains est donnée sous forme d'une liste de couples de nombres : pour chaque train on fournit son heure d'arrivée en gare et son heure de départ. Afin de simplifier les notations, on ne considère que des heures entières.
On garantit que l'heure d'arrivée d'un train est toujours strictement inférieure à son heure de départ.
Exemple
trains = [(3, 5), (2, 4), (6, 8)]
Trois trains vont passer en gare dans la journée :
-
le train A arrivera à 3h et repartira à 5h,
-
le train B arrivera à 2h et repartira à 4h,
-
le train C arrivera à 6h et repartira à 8h.
Pas d'accident !
Les heures d'arrivée et de départ tiennent compte des temps de freinage et d'accélération des trains.
Si, par exemple, un train quitte la gare à 13h, un autre peut tout à fait prendre sa place à 13h pile !
Lorsqu'un train est en gare, il est stationné le long d'un quai et n'en bouge pas. Chaque quai ne peut accueillir qu'un seul train à la fois.
Exemples
En reprenant la liste [(3, 5), (2, 4), (6, 8)], on peut observer sur la figure suivante que les trains A et B sont présents en gare au même moment. Il y aura donc au maximum deux quais occupés en même temps.
Dans le cas [(1, 3), (6, 7), (5, 6), (3, 5)], aucun train n'est présent en gare en même temps qu'un autre. À chaque instant un seul quai est utilisé.
La première étape de la résolution consiste à construire la liste des évènements associés aux trains de la journée. On appelle « évènement » un couple de nombres contenant :
-
l'heure d'arrivée ou de départ d'un train,
-
la variation du nombre de trains présents en gare :
+1si l'heure correspond à l'arrivée d'un train,-1si c'est un départ.
Exemple
La liste des évènements :
-
associée à
[(3, 5), (2, 4), (6, 8)] -
est
[(3, 1), (5, -1), (2, 1), (4, -1), (6, 1), (8, -1)].
Dans cette liste :
-
le couple
(3, 1)indique qu'à 3h, un train arrive en gare (il y a un train de plus stationné), -
le couple
(4, -1)indique qu'à 4h, un train quitte la gare (il y a un train de moins stationné).
Une fois cette liste des évènements créée, on pourra la trier en faisant les_evenements.sort() et l'utiliser afin de calculer le nombre maximal de quais utilisés au même instant.
Tri de couples
La liste des évènements est une liste contenant des couples (horaire, variation).
Lors du tri, Python compare tout d'abord les premières valeurs de chaque couple, les horaires.
Si deux évènements se déroulent à la même heure, Python compare alors les secondes valeurs de chaque couple (les variations).
Ceci nous assure que le tri de la liste des évènements les classe dans l'ordre chronologique et que, dans le cas où deux évènements ont lieu à la même heure, ceux correspondant à des départs (associés à la variation -1) sont placés avant ceux d'arrivée (associés à la valeur +1).
Listes triées ?
Il n'est pas demandé de renvoyer une liste d'évènements triée.
Par contre, les tests comparent les versions triées de chaque liste.
Exemples
>>> trains = [(3, 5), (2, 4), (6, 8)]
>>> evenements(trains)
[(3, 1), (5, -1), (2, 1), (4, -1), (6, 1), (8, -1)]
>>> nb_maxi_quais(trains)
2
>>> trains = [(1, 3), (6, 7), (5, 6), (3, 5)]
>>> evenements(trains)
[(1, 1), (3, -1), (6, 1), (7, -1), (5, 1), (6, -1), (3, 1), (5, -1)]
>>> nb_maxi_quais(trains)
1
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)