Nombre minimal de quais

Le chef de gare a devant lui la liste des trains passant par sa gare dans la journée.

Cette liste 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.

Exemple

🐍 Console Python

trains = [(3, 5), (2, 4), (6, 8)]

Trois trains vont passer en gare dans la journée :

• le premier arrivera à 3h et repartira à 5h,

• le deuxième arrivera à 2h et repartira à 4h,

• le dernier arrivera à 6h et repartira à 8h.

On garantit :

• que l'heure de départ de chaque train est strictement supérieure à son heure d'arrivée,

• que lorsqu'un train arrive en gare ou la quitte, cet évènement est instantané. Il n'y a pas de temps de freinage ou d'accélération...

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.

Le chef de gare se demande combien de quai au minimum il va devoir utiliser dans la journée afin de pouvoir accueillir tous les trains ?

Exemples

En reprenant la liste [(3, 5), (2, 4), (6, 8)], il est possible de n'utiliser que 2 quais.

Dans le cas [(1, 5), (6, 7), (5, 5.99)], il est possible de n'utiliser qu'un seul quai.

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 : 1 si l'heure correspond à l'arrivée d'un train, -1 si 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 et l'utiliser afin de calculer le nombre minimal de quais nécessaires.

Exemples

🐍 Console Python

>>> trains = [(3, 5), (2, 4), (6, 8)]
>>> nb_min_quais(trains)
2
>>> trains = [(1, 5), (6, 7), (5, 5.99)]
>>> nb_min_quais(trains)
1
>>> trains = [(1, 2), (2, 3), (3, 4), (4, 5)]
>>> nb_min_quais(trains)
1
>>> trains = []
>>> nb_min_quais(trains)
0

Lancer# Testsbksl-nltrains = [(3, 5), (2, 4), (6, 8)]bksl-nlassert nbpy-undminpy-undquais(trains) == 2bksl-nlbksl-nltrains = [(1, 5), (6, 7), (5, 5.99)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = [(1, 2), (2, 3), (3, 4), (4, 5)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = []bksl-nlassert nbpy-undminpy-undquais(trains) == 0bksl-nlbksl-nlbksl-nl# Tests secretsbksl-nltrains = [(k, k+1) for k in range(50)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = [(k, k+1) for k in range(20, 0, -1)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = [(k, k+2) for k in range(50)]bksl-nlassert nbpy-undminpy-undquais(trains) == 2bksl-nlbksl-nltrains = [(0, 20-k) for k in range(10)]bksl-nlassert nbpy-undminpy-undquais(trains) == 10bksl-nlbksl-nl Valider ∞/∞ TéléchargerTéléverser RechargerSauvegarder

def listepy-undevenements(trains):bksl-nl evenements = []bksl-nl for (arrivee, depart) in ...:bksl-nl evenements.append((..., ...))bksl-nl evenements.append((..., ...))bksl-nl return evenementsbksl-nlbksl-nlbksl-nldef nbpy-undminpy-undquais(trains):bksl-nl evenements = listepy-undevenements(trains)bksl-nl evenements.sort() # tri de la liste des évènementsbksl-nl # en cas d'égalité, les départs sont en premiersbksl-nlbksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nltrains = [(3, 5), (2, 4), (6, 8)]bksl-nlassert nbpy-undminpy-undquais(trains) == 2bksl-nlbksl-nltrains = [(1, 5), (6, 7), (5, 5.99)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = [(1, 2), (2, 3), (3, 4), (4, 5)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = []bksl-nlassert nbpy-undminpy-undquais(trains) == 0bksl-nlbksl-nldef listepy-undevenements(trains):bksl-nl evenements = []bksl-nl for (arrivee, depart) in trains:bksl-nl evenements.append((arrivee, +1))bksl-nl evenements.append((depart, -1))bksl-nl return evenementsbksl-nlbksl-nlbksl-nldef nbpy-undminpy-undquais(trains):bksl-nl evenements = listepy-undevenements(trains)bksl-nl evenements.sort() # tri de la liste des évènementsbksl-nl # en cas d'égalité, les départs sont en premiersbksl-nlbksl-nl nbpy-undquaispy-undoccupes = 0bksl-nl nbpy-undmini = 0bksl-nl for (horaire, variation) in evenements:bksl-nl nbpy-undquaispy-undoccupes += variationbksl-nl if nbpy-undquaispy-undoccupes > nbpy-undmini:bksl-nl nbpy-undmini = nbpy-undquaispy-undoccupesbksl-nl return nbpy-undminibksl-nlbksl-nlbksl-nl# Testsbksl-nltrains = [(3, 5), (2, 4), (6, 8)]bksl-nlassert nbpy-undminpy-undquais(trains) == 2bksl-nlbksl-nltrains = [(1, 5), (6, 7), (5, 5.99)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = [(1, 2), (2, 3), (3, 4), (4, 5)]bksl-nlassert nbpy-undminpy-undquais(trains) == 1bksl-nlbksl-nltrains = []bksl-nlassert nbpy-undminpy-undquais(trains) == 0bksl-nlbksl-nl

A

Une solution possible

{{ IDE('exo_corr') }}

Une fois la liste des évènements créée, on la trie. Le choix des valeurs +1 pour les arrivées et -1 pour les départs permet d'assurer qu'en cas d'horaires identiques, les évènements de départs seront envisagés avant ceux d'arrivée. On libère ainsi les quais en priorité.

Une fois ce tri effectué, on parcourt les évènements dans l'ordre chronologique :

• pour chaque évènement, on modifie la valeur du nombre de quais utilisés à l'aide de la variation associée à l'évènement,
• on vérifie ensuite que l'on n'a pas dépassé le nombre minimal de quais nécessaires. Si c'est le cas on met à jour la valeur.

A la fin du parcours, on renvoie le nombre minimal de quais à utiliser.

Z