Meeting Rooms

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

Le tri des réunions par heure de début coûte O(n log n) , et le parcours qui compare les éléments voisins coûte O(n) , donc le coût total est O(n log n) . Comparer chaque paire coûte plutôt O(n²) .

Q: Pourquoi suffit-il de comparer chaque réunion à celle qui la précède ?

Après le tri par heure de début, si aucun chevauchement n’a été trouvé jusqu’à présent, les réunions considérées jusque-là forment une chaîne dans laquelle chacune commence à l’heure de fin de la précédente ou après. La dernière de la chaîne se termine le plus tard. Une nouvelle réunion qui commence à l’heure de fin de celle-ci ou après ne peut chevaucher aucune des réunions précédentes.

Q: Les réunions qui se touchent se chevauchent-elles ?

Pas dans ce problème : une réunion peut commencer exactement au moment où une autre se termine. C’est pourquoi la vérification est start < previous end . Si les réunions qui se chevauchent étaient interdites, la vérification deviendrait start ≤ previous end .

Q: Comment trouver le nombre minimum de salles de réunion ?

Triez les heures de début et les heures de fin dans deux listes distinctes, puis parcourez-les toutes les deux : chaque début ouvre une salle, et chaque fin qui survient avant ou au même moment que le début suivant en libère une. Le nombre maximal de salles ouvertes simultanément est la réponse. Répondre ici par oui ou non revient à demander si une seule salle suffit.

FacileIntervalles Tri

+10

Tu reçois une liste de réunions sous forme de deux tableaux : la réunion i se déroule de starts[i] à ends[i]. Une personne souhaite assister à toutes les réunions, donc aucune paire de réunions ne peut se chevaucher. Une réunion peut commencer au moment exact où une autre se termine. Renvoie true si la personne peut assister à toutes les réunions, et false sinon.

Fonction

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

startsinteger-array: l’heure de début de chaque réunion
endsinteger-array: l'heure de fin de chaque réunion, au même indice que son heure de début
Renvoieboolean: vrai si aucune réunion ne se chevauche, faux sinon

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 = [9, 13, 10]ends = [10, 15, 12]
Sortie: true
Explication: Dans l’ordre chronologique, les réunions se déroulent de 9 à 10, de 10 à 12 et de 13 à 15. La deuxième commence au moment où la première se termine, ce qui est autorisé. La réponse est donc true.

Entrée: starts = [1, 4, 7]ends = [5, 6, 8]
Sortie: false
Explication: La réunion de 1 à 5 est toujours en cours à 4, lorsque la réunion de 4 à 6 commence, donc la réponse est false.

+15 tests cachés à la soumission

Pour aller plus loin

Si les réunions sont réservées une par une, comment vérifier chaque nouvelle réservation par rapport au calendrier en O(log n), sans tout trier à nouveau ?

Solution

Vérifier chaque paire de réunions permet de repérer tout chevauchement, mais cela coûte O(n²). Le tri par heure de début change la donne : une réunion ne peut alors chevaucher que sa voisine dans l’ordre trié, donc une seule comparaison par réunion suffit.

Comparez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Deux réunions se chevauchent lorsque chacune commence avant que l’autre ne se termine. Pour les réunions de 1 à 5 et de 4 à 6 : 1 est avant 6 et 4 est avant 5, donc elles se chevauchent. Pour les réunions de 9 à 10 et de 10 à 12 : 10 n’est pas avant 10, donc elles se touchent seulement.

Utiliser < strictement des deux côtés permet à une réunion de commencer exactement au moment où une autre se termine. Effectue le test sur chaque paire et renvoie false dès le premier chevauchement.

Le problème, c’est le nombre de paires. Avec n = 5000 réunions, il y a environ 12,5 millions de paires, et un emploi du temps sans chevauchement t’oblige à toutes les vérifier, ce qui est trop lent pour les tests les plus volumineux.

Algorithme

Pour chaque indice i, et chaque indice j qui le suit :
Si starts[i] < ends[j] et starts[j] < ends[i], les deux réunions se chevauchent : renvoie false.
Si aucune paire ne se chevauche, renvoie true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Trier par début et vérifier les voisins

Intuition

Trie les réunions par heure de début, en gardant chaque début associé à sa propre fin. Examine ensuite n’importe quelle réunion et celle qui la précède immédiatement. Si la réunion précédente se termine après le début de la suivante, elles se chevauchent. Sinon, la réunion suivante commence au moment où la précédente se termine ou après.

Pourquoi suffit-il de vérifier uniquement la réunion voisine ? Si chaque réunion examinée jusqu’ici commence au moment où la précédente se termine ou après, elles ne se chevauchent jamais, et celle qui précède immédiatement est celle qui se termine le plus tard. Une nouvelle réunion qui commence au moment où elle se termine ou après commence au moment où toutes les autres se terminent ou après.

Dans le premier exemple, les réunions triées sont de 9 à 10, de 10 à 12, et de 13 à 15. Le début 10 n’est pas antérieur à la fin 10, et le début 13 n’est pas antérieur à la fin 12 : il n’y a donc pas de chevauchement. Des heures de début égales entraînent toujours un chevauchement, puisque chaque réunion dure au moins une unité, et cette vérification le détecte aussi.

Le tri coûte O(n log n) et le parcours coûte O(n). La copie des réunions sous forme de paires nécessite un espace de O(n).

Algorithme

Associez chaque début à sa fin.
Triez les paires par heure de début.
Pour chaque réunion après la première, comparez son heure de début à l’heure de fin de la réunion précédente.
Si l’heure de début est antérieure, retournez false.
Après la boucle, retournez true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Pièges et cas limites

Les erreurs courantes concernent les extrémités comparées et la façon de traiter les réunions qui se touchent.

Trier starts et laisser ends dans l’ordre d’entrée. Chaque heure de fin doit rester associée à sa propre heure de début, sinon tu compares une heure de début à l’heure de fin d’une autre réunion.
Utiliser ≤ au lieu de <. Les réunions de 9 à 10 et de 10 à 12 se touchent, mais ne se chevauchent pas, et la réponse dans ce cas est true.
Vérifier uniquement que chaque réunion se termine avant le début de la suivante dans l’ordre d’entrée. Les données d’entrée ne sont pas triées, donc les réunions voisines dans l’entrée ne donnent aucune indication.
Écrire le test par paire avec une seule condition, comme starts[j] < ends[i]. Cela ne fonctionne que lorsque la réunion j commence plus tard ; pour les réunions de 5 à 6 et de 0 à 1, dans cet ordre, 0 < 6 signale un conflit qui n’existe pas.

Questions fréquentes4

Quelle est la complexité temporelle de Meeting Rooms ?

Le tri des réunions par heure de début coûte O(n log n), et le parcours qui compare les éléments voisins coûte O(n), donc le coût total est O(n log n). Comparer chaque paire coûte plutôt O(n²).

Pourquoi suffit-il de comparer chaque réunion à celle qui la précède ?

Après le tri par heure de début, si aucun chevauchement n’a été trouvé jusqu’à présent, les réunions considérées jusque-là forment une chaîne dans laquelle chacune commence à l’heure de fin de la précédente ou après. La dernière de la chaîne se termine le plus tard. Une nouvelle réunion qui commence à l’heure de fin de celle-ci ou après ne peut chevaucher aucune des réunions précédentes.

Les réunions qui se touchent se chevauchent-elles ?

Pas dans ce problème : une réunion peut commencer exactement au moment où une autre se termine. C’est pourquoi la vérification est start < previous end. Si les réunions qui se chevauchent étaient interdites, la vérification deviendrait start ≤ previous end.

Comment trouver le nombre minimum de salles de réunion ?

Triez les heures de début et les heures de fin dans deux listes distinctes, puis parcourez-les toutes les deux : chaque début ouvre une salle, et chaque fin qui survient avant ou au même moment que le début suivant en libère une. Le nombre maximal de salles ouvertes simultanément est la réponse. Répondre ici par oui ou non revient à demander si une seule salle suffit.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

starts = [9, 13, 10]
ends = [10, 15, 12]

Attendu

true