Meeting Rooms II

Q: Quelle est la complexité temporelle de Meeting Rooms II ?

Les deux solutions rapides s’exécutent en O(n log n) . La version avec tas trie les réunions et effectue une opération sur le tas en O(log n) par réunion ; la version avec deux listes effectue deux tris et un parcours en O(n) . Les deux utilisent un espace supplémentaire de O(n) . Compter les réunions en cours à chaque début prend O(n²) .

MoyenIntervalles Tas Tri

+10

Vous recevez une liste de réunions sous forme de deux tableaux : la réunion i se déroule de starts[i] à ends[i]. Une salle accueille une seule réunion à la fois, et une réunion peut commencer dans une salle au moment exact où une autre réunion qui s’y déroule se termine.

Écrivez une fonction nommée minMeetingRooms qui renvoie le plus petit nombre de salles pouvant accueillir toutes les réunions.

Fonction

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

startsinteger-array: l’heure de début de chaque réunion
endsinteger-array: l'heure de fin de chaque réunion, au même index que son heure de début
Renvoieinteger: le nombre minimal de salles pouvant accueillir toutes les réunions

Contraintes

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Les réunions ne sont pas triées. Deux réunions peuvent être identiques.

Exemples

Entrée: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Sortie: 3
Explication: À l’heure 4, les réunions de 1 à 5, de 2 à 6 et de 4 à 8 sont toutes en cours, donc tu as besoin d’au moins 3 salles. Trois suffisent : la réunion de 7 à 9 prend la salle qui se libère à 5.

Entrée: starts = [0, 2, 3]ends = [10, 3, 5]
Sortie: 2
Explication: La réunion de 0 à 10 occupe une salle pendant toute sa durée. La réunion de 2 à 3 a besoin d’une deuxième salle, et celle de 3 à 5 prend cette même salle dès qu’elle se libère, donc 2 salles suffisent.

+17 tests cachés à la soumission

Pour aller plus loin

Peux-tu aussi indiquer dans quelle salle se déroule chaque réunion, sans utiliser plus de salles que le nombre indiqué dans la réponse ?

Solution

Le nombre de salles dont vous avez besoin correspond au nombre maximal de réunions qui se déroulent au même moment. Compter les réunions en cours à chaque heure de début permet de le trouver en O(n²). Le tri transforme la question en un seul parcours de la journée : un tas min des heures auxquelles les salles se libèrent, ou deux listes triées des heures de début et de fin, donne la réponse en O(n log n).

Compter les réunions en cours à chaque heure de début

Correcte, mais ne termine pas sur les plus gros tests

Intuition

À tout moment, chaque réunion en cours a besoin de sa propre salle. Il faut donc au moins autant de salles que le nombre maximal de réunions en cours simultanément. Ce nombre est également suffisant : attribuez les salles dans l’ordre des heures de début, et une nouvelle salle ne sera ouverte que lorsque toutes les salles seront occupées, ce qui signifie que ce nombre de réunions est alors en cours.

Le nombre de réunions en cours n’augmente qu’au début d’une réunion, donc le moment le plus chargé correspond au début d’une réunion. Pour chaque réunion i, comptez les réunions j telles que starts[j] ≤ starts[i] < ends[j] : elles ont commencé et ne sont pas encore terminées. Une réunion qui se termine exactement à starts[i] n’est pas comptée, car sa salle est de nouveau libre à ce moment-là.

Dans le premier exemple, à l’instant 4, les réunions de 1 à 5, de 2 à 6 et de 4 à 8 sont en cours : 3. À l’instant 7, seules celles de 4 à 8 et de 7 à 9 le sont : 2. Le nombre maximal est 3.

Chacune des n réunions parcourt les n réunions. Avec n = 5000, cela représente 25 millions de vérifications : une fraction de seconde en C, plusieurs secondes en Python ou R, et quatre fois plus à chaque fois que n double.

Algorithme

Pour chaque réunion i, définissez running à 0.
Pour chaque réunion j, ajoutez 1 à running lorsque starts[j] ≤ starts[i] < ends[j].
Conservez la plus grande valeur de running que vous ayez vue.
Renvoyez cette plus grande valeur.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

Tas min-heap des heures auxquelles les salles se libèrent

Intuition

Attribuez les salles comme le ferait une personne à l’accueil. Prenez les réunions dans l’ordre de leur heure de début. Pour chacune, regardez la salle qui se libère en premier. Si elle est libre au moment où la réunion commence, la réunion obtient cette salle. Sinon, toutes les salles sont encore occupées, alors vous en ouvrez une nouvelle.

Vérifier uniquement cette salle est sans risque. Si la salle qui se libère en premier est encore occupée, elles le sont toutes. Si elle est libre, n’importe quelle salle libre convient tout aussi bien : les réunions à venir commencent à cette heure ou plus tard, donc toutes les salles qui sont libres maintenant le resteront pour toutes ces réunions.

Vous avez besoin de connaître l’heure de libération la plus proche parmi les salles, et elle change après chaque réunion. Un tas min conserve une heure de fin par salle et vous donne la plus petite. Réutiliser une salle remplace son heure de fin par celle de la nouvelle réunion ; ouvrir une salle ajoute une nouvelle heure de fin. Dans le premier exemple, après le tri par heure de début : 1 à 5 donne [5], 2 à 6 donne [5, 6], 4 à 8 donne [5, 6, 8], et 7 à 9 trouve 5 inférieur ou égal à 7 et le remplace, ce qui laisse [6, 8, 9]. Trois salles.

Le tri coûte O(n log n) et chaque réunion nécessite une opération sur le tas en O(log n). heapq en Python, PriorityQueue en Java, priority_queue avec greater en C++, BinaryHeap avec Reverse en Rust, container/heap en Go et SplMinHeap en PHP vous fournissent le tas. Dans les autres langages, vous le gérez dans un tableau : le parent de l’indice i se trouve à (i-1)/2, et une valeur remonte tant qu’elle est plus petite que son parent.

Algorithme

Trie les réunions par heure de début, en conservant chaque heure de début avec sa propre heure de fin.
Pour chaque réunion, si le tas n'est pas vide et que sa plus petite heure de fin est antérieure ou égale à l'heure de début de la réunion, remplace cette heure de fin par l'heure de fin de la réunion.
Sinon, ajoute l'heure de fin de la réunion au tas : une nouvelle salle est ouverte.
Renvoie la taille du tas, avec une entrée par salle.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

Trier séparément les débuts et les fins

Intuition

Le tas retient quelle heure de fin correspond à quelle salle, mais la réponse n’est qu’un décompte. Lorsqu’une réunion commence, tout ce qui compte, c’est de savoir si une réunion s’est terminée à ce moment-là ou avant et a libéré une salle ; peu importe laquelle. Triez donc les heures de début et de fin dans deux listes distinctes, puis parcourez les heures de début à l’aide d’un pointeur ended dans la liste des heures de fin.

Pour chaque heure de début, dans l’ordre : si elle est supérieure ou égale à endTimes[ended], une réunion est terminée à ce moment-là. Sa salle accueille la nouvelle réunion, et ended avance. Sinon, toutes les salles utilisées sont encore occupées, et rooms augmente de un. Chaque début utilise au plus une heure de fin, de la même manière qu’une salle réutilisée dans le tas remplace une ancienne heure de fin par une nouvelle.

Dans le premier exemple, les heures de début sont 1, 2, 4, 7 et les heures de fin 5, 6, 8, 9. Les heures de début 1, 2 et 4 précèdent toutes l’heure de fin 5, donc rooms atteint 3. L’heure de début 7 est supérieure ou égale à 5, elle réutilise donc cette salle et ended avance jusqu’à l’heure de fin 6. La réponse est 3. Le symbole ≥ permet aux réunions qui se chevauchent juste de partager une salle : dans le deuxième exemple, l’heure de début 12 correspond à l’heure de fin 12 et réutilise cette salle.

Le décompte ne dépasse jamais le véritable maximum : lorsque rooms augmente, la prochaine heure de fin est encore à venir, donc toutes les réunions dans rooms salles sont en cours à cet instant. Il atteint également le maximum, car une heure de début n’évite d’ouvrir une salle que lorsqu’une véritable heure de fin, égale ou antérieure, en a libéré une. Les deux tris coûtent O(n log n), le parcours O(n), et les copies triées utilisent O(n) d’espace.

Algorithme

Triez une copie des heures de début et une copie des heures de fin.
Définissez rooms et ended à 0.
Pour chaque heure de début dans l’ordre, si elle est égale ou postérieure à endTimes[ended], ajoutez 1 à ended : la réunion prend une salle libérée.
Sinon, ajoutez 1 à rooms.
Renvoyez rooms.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

Pièges et cas limites

La plupart des bugs se trouvent dans la comparaison au moment où deux réunions se touchent, ou dans le choix de la salle vérifiée.

Vérifier start > end au lieu de start ≥ end. Une réunion ne peut alors pas utiliser une salle au moment où elle se libère, et les réunions de 10 à 12, de 12 à 14 et de 14 à 16 nécessitent 2 salles au lieu d’1.
Vérifier la dernière salle ouverte au lieu de celle qui se libère en premier. Pour les réunions de 1 à 3, de 2 à 10 et de 4 à 6, la dernière salle ouverte est occupée jusqu’à 10, donc tu ouvres une troisième salle alors que la première est libre depuis 3.
Prendre le plus grand nombre de réunions qui chevauchent une réunion, puis ajouter 1. La réunion de 0 à 10 chevauche celles de 2 à 3 et de 3 à 5, mais ces deux réunions ne se chevauchent pas entre elles : 2 salles suffisent donc, et non 3.
Confondre les deux approches avec tri. Le tas nécessite que chaque heure de fin soit associée à sa propre heure de début avant le tri par heure de début ; l’approche avec deux listes trie volontairement les heures de début et les heures de fin séparément.

Questions fréquentes4

Quelle est la complexité temporelle de Meeting Rooms II ?

Les deux solutions rapides s’exécutent en O(n log n). La version avec tas trie les réunions et effectue une opération sur le tas en O(log n) par réunion ; la version avec deux listes effectue deux tris et un parcours en O(n). Les deux utilisent un espace supplémentaire de O(n). Compter les réunions en cours à chaque début prend O(n²).

Pourquoi un tas min résout-il le problème Meeting Rooms II ?

En prenant les réunions dans l’ordre de leur début, la seule salle qu’il vaut la peine de vérifier est celle qui se libère en premier. Un tas min des heures de fin permet de trouver cette salle en O(1) et de le mettre à jour en O(log n). Le tas ne grandit que lorsque toutes les salles sont occupées, donc sa taille finale correspond au nombre minimal de salles nécessaires.

Peut-on résoudre Meeting Rooms II sans tas ?

Oui. Triez les heures de début et les heures de fin dans deux listes distinctes, puis parcourez les débuts avec un pointeur dans la liste des fins. Un début qui a lieu à l’heure de la prochaine fin inutilisée ou après réutilise une salle ; tout autre début en ouvre une. La même idée fonctionne avec une ligne de balayage : transformez chaque réunion en un événement +1 à son début et en un événement -1 à sa fin, traitez les fins avant les débuts aux mêmes heures et suivez le total cumulé maximal.

La réponse est-elle identique au nombre maximal de réunions qui se chevauchent à un même moment ?

Oui. Les réunions qui se déroulent au même moment ont besoin de salles différentes, il en faut donc au moins autant. Attribuer à chaque réunion, dans l’ordre de début, n’importe quelle salle libre ne nécessite jamais plus de salles, donc le nombre maximal de réunions simultanées correspond exactement à la réponse.

Python

def minMeetingRooms(starts, ends):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

Attendu

Meeting Rooms II

Fonction

Contraintes

Exemples

Indices

Solution

Compter les réunions en cours à chaque heure de début

Tas min-heap des heures auxquelles les salles se libèrent

Trier séparément les débuts et les fins

Pièges et cas limites

Questions fréquentes4

Problèmes similaires