Minimum Platforms

Q: Quelle est la complexité temporelle du problème du nombre minimal de quais ?

Le tri des deux tableaux coûte O(n log n) et le balayage qui suit coûte O(n) ; les tris dominent donc. Les copies triées nécessitent un espace supplémentaire de O(n) .

Q: En quoi le problème du nombre minimal de quais est-il différent de celui des salles de réunion II ?

Les deux demandent le nombre maximal d’intervalles qui se chevauchent à un même instant. Ici, un train occupe son quai jusqu’à la minute où il part ; dans Meeting Rooms II, une salle est libre dès que sa réunion se termine. Dans le balayage, cela se résume à une comparaison : en cas d’égalité, tu traites d’abord l’arrivée ici, et la réunion qui se termine là-bas.

Q: Peut-on résoudre le problème du nombre minimal de quais sans trier ?

Oui, puisque chaque horaire correspond à une heure fixe. Indexez les compteurs de 2401 éléments avec le nombre HHMM , ajoutez 1 à chaque arrivée et soustrayez 1 à departure + 1 . La somme cumulée maximale est la réponse : O(n + 2400) en temps. Les index tels que 1260 à 1299 ne correspondent pas à des heures valides et ne reçoivent aucune arrivée ; ils ne déterminent donc jamais un pic.

MoyenTri Glouton Deux pointeurs

+10

Une gare dispose de l’horaire d’une journée : le train i arrive à arrival[i] et part à departure[i]. Les heures sont des nombres au format HHMM, l’heure sans les deux-points, donc 930 correspond à 09:30.

Un train occupe son quai à partir de la minute où il arrive jusqu’à celle où il part, ces deux minutes incluses. Ainsi, un train qui arrive à la minute où un autre part ne peut pas prendre le quai de ce train.

Renvoyez le nombre minimal de quais dont la gare a besoin pour qu’aucun train n’ait à attendre.

Fonction

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: l’heure d’arrivée de chaque train, sous la forme d’un nombre HHMM
departureinteger-array: l’heure de départ de chaque train, sous la forme d’un nombre HHMM ; departure[i] correspond à arrival[i]
Renvoieinteger: le plus grand nombre de trains présents à la gare au cours de la même minute, soit le nombre minimal de quais nécessaires

Contraintes

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Chaque heure est une heure HHMM valide : ses deux derniers chiffres sont au plus égaux à 59.
Tous les trains circulent le même jour. Les tableaux ne sont pas triés.

Exemples

Entrée: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Sortie: 3
Explication: À 15:30, trois trains sont à la gare : ceux de 15:00 à 16:00, de 15:20 à 15:35 et de 15:30 à 15:45. Il n’y a aucune minute où il y en a quatre, donc 3 quais suffisent.

Entrée: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Sortie: 2
Explication: Le train qui arrive à 12:30 croise celui qui part à 12:30, et la même chose se produit à 13:00. À chacune de ces minutes, deux trains se trouvent à la gare, donc la réponse est 2, et non 1.

Entrée: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Sortie: 2
Explication: Le train de 06:00 à 22:00 occupe une voie toute la journée. Les trains de 07:00 à 07:15 et de 13:00 à 14:00 ne se croisent jamais, ils partagent donc une deuxième voie : 2.

Pour aller plus loin

Certains trains de nuit arrivent avant minuit et repartent après, si bien que leur heure de départ est inférieure à leur heure d’arrivée. Comment compteriez-vous les quais lorsque l’horaire passe minuit ?

Solution

La réponse est le nombre maximal de trains présents à la gare à la même minute. Il s’agit de trouver la minute la plus fréquentée sans comparer chaque paire de trains. Trie séparément les arrivées et les départs, puis parcours une fois les événements de la journée en maintenant un compteur pour la trouver en O(n log n).

Comptez les trains à chaque arrivée

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Les trains présents pendant la même minute ont tous besoin de quais différents : la minute la plus chargée donne donc une borne inférieure. C’est aussi suffisant : on ouvre un nouveau quai uniquement lorsqu’un train à l’arrivée trouve tous les quais ouverts occupés. À cette minute-là, un train se trouve sur chacun des quais ouverts, ainsi que sur le nouveau : on n’ouvre donc jamais plus de quais que le pic.

Le nombre de trains présents n’augmente qu’à l’arrivée d’un train : la minute la plus chargée correspond donc à la minute d’arrivée d’un train. Pour chaque train i, compte les trains j tels que arrival[j] ≤ arrival[i] ≤ departure[j]. Les deux comparaisons utilisent ≤, car un train occupe encore son quai pendant la minute où il part.

Chacun des n trains vérifie les n autres : le travail est donc de O(n²), soit 25 millions de vérifications de paires pour 5000 trains.

Algorithme

Définis most = 0.
Pour chaque train i, compte les trains j tels que arrival[j] ≤ arrival[i] ≤ departure[j].
Si ce nombre est supérieur à most, stocke-le.
Renvoie most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

Trier les deux listes et les parcourir avec deux pointeurs

Intuition

Le nombre de trains présents dépend uniquement du nombre de trains arrivés et du nombre de trains partis à une minute donnée, et non du moment où chaque train part. Triez donc les heures d’arrivée et de départ dans deux listes indépendantes. Lues ensemble dans l’ordre chronologique, elles représentent les événements de la journée : une arrivée ajoute un train, un départ en retire un.

En cas d’égalité, l’arrivée passe en premier, car le train qui part occupe encore son quai pendant cette minute. Dans le premier exemple, le compte revient à 0 après le départ à 1100, puis les arrivées à 1500, 1520 et 1530 ont toutes lieu avant le départ à 1535, ce qui le fait atteindre 3.

Une fois toutes les arrivées traitées, les départs restants ne peuvent que faire baisser le compte : le parcours s’arrête donc là. Le tri coûte O(n log n) et le parcours prend au plus 2n étapes.

Algorithme

Triez une copie de arrival et une copie de departure.
Initialisez platforms, most, i et j à 0.
Tant que i < n : si arrivals[i] ≤ departures[j], ajoutez 1 à platforms, mettez à jour most et avancez i.
Sinon, soustrayez 1 de platforms et avancez j.
Retournez most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

Pièges et cas limites

Comparer avec < alors que la règle inclusive nécessite ≤. Dans le deuxième exemple, chaque train qui arrive prend alors le quai du train qui part à cette minute, et la réponse passe de 2 à 1.
Soustraire des nombres HHMM : 1300 moins 1259 donne 41, alors que les heures sont espacées d’une minute. Il est sans risque de les comparer, et la solution se contente de les comparer.
Trier les trains par heure d’arrivée et comparer chacun uniquement avec le train qui le précède. Un long arrêt, comme de 06:00 à 22:00 dans le troisième exemple, chevauche des trains beaucoup plus loin dans la liste.
Ignorer les trains qui arrivent et partent à la même minute. Quatre trains qui restent chacun de 10:00 à 10:00 ont besoin de quatre quais.

Questions fréquentes3

Quelle est la complexité temporelle du problème du nombre minimal de quais ?

Le tri des deux tableaux coûte O(n log n) et le balayage qui suit coûte O(n) ; les tris dominent donc. Les copies triées nécessitent un espace supplémentaire de O(n).

En quoi le problème du nombre minimal de quais est-il différent de celui des salles de réunion II ?

Les deux demandent le nombre maximal d’intervalles qui se chevauchent à un même instant. Ici, un train occupe son quai jusqu’à la minute où il part ; dans Meeting Rooms II, une salle est libre dès que sa réunion se termine. Dans le balayage, cela se résume à une comparaison : en cas d’égalité, tu traites d’abord l’arrivée ici, et la réunion qui se termine là-bas.

Peut-on résoudre le problème du nombre minimal de quais sans trier ?

Oui, puisque chaque horaire correspond à une heure fixe. Indexez les compteurs de 2401 éléments avec le nombre HHMM, ajoutez 1 à chaque arrivée et soustrayez 1 à departure + 1. La somme cumulée maximale est la réponse : O(n + 2400) en temps. Les index tels que 1260 à 1299 ne correspondent pas à des heures valides et ne reçoivent aucune arrivée ; ils ne déterminent donc jamais un pic.

def minimumPlatforms(arrival, departure):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

Résultat attendu