Aller au contenu

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
🐍 Script Python
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.

Premier exemple

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é.

Second exemple

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 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
🐍 Console Python
>>> 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
🐍 Console Python
>>> 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
###
# Testsbksl-nltrains = [(3, 5), (2, 4), (6, 8)]bksl-nlassert sorted(evenements(trains)) == [(2, 1), (3, 1), (4, -1), (5, -1), (6, 1), (8, -1)]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 2bksl-nlbksl-nltrains = [(1, 3), (6, 7), (5, 6), (3, 5)]bksl-nlassert sorted(evenements(trains)) == [bksl-nl (1, 1),bksl-nl (3, -1),bksl-nl (3, 1),bksl-nl (5, -1),bksl-nl (5, 1),bksl-nl (6, -1),bksl-nl (6, 1),bksl-nl (7, -1),bksl-nl]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 1bksl-nlbksl-nlbksl-nl# Tests supplémentairesbksl-nlassert evenements([]) == [], "Erreur avec une liste vide"bksl-nlassert nbpy-undmaxipy-undquais([]) == 0, "Erreur avec une liste vide"bksl-nlbksl-nltrains = [(k, k + 1) for k in range(50)]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 1, f"Erreur avec {trains = }"bksl-nlbksl-nltrains = [(k, k + 1) for k in range(20, 0, -1)]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 1, f"Erreur avec {trains = }"bksl-nlbksl-nltrains = [(k, k + 2) for k in range(50)]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 2, f"Erreur avec {trains = }"bksl-nlbksl-nltrains = [(0, 20 - k) for k in range(10)]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 10, f"Erreur avec {trains = }"bksl-nlbksl-nlfrom functools import reducebksl-nlfrom random import randrangebksl-nlbksl-nlbksl-nldef nbpy-undmaxipy-undquaispy-undcorr(trains):bksl-nl lespy-undevenements = reduce(bksl-nl lambda evts, train: evts + [(train[0], 1), (train[1], -1)], trains, []bksl-nl )bksl-nl lespy-undevenements.sort()bksl-nl quaispy-undoccupes = 0bksl-nl maxi = 0bksl-nl for (py-und, variation) in lespy-undevenements:bksl-nl quaispy-undoccupes += variationbksl-nl if quaispy-undoccupes > maxi:bksl-nl maxi = quaispy-undoccupesbksl-nl return lespy-undevenements, maxibksl-nlbksl-nlbksl-nlfor test in range(20):bksl-nl nbpy-undtrains = randrange(20, 50)bksl-nl trains = []bksl-nl for unpy-undtrain in range(nbpy-undtrains):bksl-nl arrivee = randrange(0, 2 py-str nbpy-undtrains)bksl-nl depart = arrivee + randrange(1, 10)bksl-nl trains.append((arrivee, depart))bksl-nl evtspy-undattendus, quaispy-undattendus = nbpy-undmaxipy-undquaispy-undcorr(trains)bksl-nl assert (bksl-nl sorted(evenements(trains)) == evtspy-undattendusbksl-nl ), f"Erreur avec les trains {trains}"bksl-nl assert nbpy-undmaxipy-undquais(trains) == quaispy-undattendus, f"Erreur avec les trains {trains}"bksl-nlbksl-nl 5/5

def evenements(trains):bksl-nl lespy-undevenements = []bksl-nl for (arrivee, depart) in ...:bksl-nl lespy-undevenements.append((..., ...))bksl-nl lespy-undevenements.append((..., ...))bksl-nl return lespy-undevenementsbksl-nlbksl-nlbksl-nldef nbpy-undmaxipy-undquais(trains):bksl-nl lespy-undevenements = evenements(trains)bksl-nl lespy-undevenements.sort()bksl-nlbksl-nl nbpy-undquaispy-undoccupes = 0bksl-nl maxi = 0bksl-nl for (horaire, variation) in ...:bksl-nl ...bksl-nlbksl-nl return ...bksl-nlbksl-nlbksl-nl# Testsbksl-nltrains = [(3, 5), (2, 4), (6, 8)]bksl-nlassert sorted(evenements(trains)) == [(2, 1), (3, 1), (4, -1), (5, -1), (6, 1), (8, -1)]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 2bksl-nlbksl-nltrains = [(1, 3), (6, 7), (5, 6), (3, 5)]bksl-nlassert sorted(evenements(trains)) == [bksl-nl (1, 1),bksl-nl (3, -1),bksl-nl (3, 1),bksl-nl (5, -1),bksl-nl (5, 1),bksl-nl (6, -1),bksl-nl (6, 1),bksl-nl (7, -1),bksl-nl]bksl-nlassert nbpy-undmaxipy-undquais(trains) == 1bksl-nlbksl-nldef evenements(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-undmaxipy-undquais(trains):bksl-nl lespy-undevenements = evenements(trains)bksl-nl lespy-undevenements.sort()bksl-nlbksl-nl nbpy-undquaispy-undoccupes = 0bksl-nl maxi = 0bksl-nl for (horaire, variation) in lespy-undevenements:bksl-nl nbpy-undquaispy-undoccupes += variationbksl-nl if nbpy-undquaispy-undoccupes > maxi:bksl-nl maxi = nbpy-undquaispy-undoccupesbksl-nl return maxibksl-nlbksl-nl

A

Remarques⚓︎

Ce problème fait partie de la grande famille des problèmes d'optimisation de tâches. On peut utiliser un algorithme équivalent pour déterminer par exemple le nombre de collaborateurs devant travailler en même temps sur diverses tâches partagées.

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 maximal de quais occupés. Si c'est le cas on met à jour la valeur maxi.

À la fin du parcours, on renvoie le nombre de quais maximal.

Z