Asistir a todas las reuniones
La misión
Problema
Un calendario lista reuniones como pares [start, end], sin ningún orden en particular. Decide si una persona puede estar en todas las reuniones de principio a fin. Una reunión que termina justo cuando empieza otra no es un problema, porque la persona puede pasar directamente de una a la siguiente.
Ejemplos
Input: meetings = [[0, 30], [5, 10], [15, 20]]
Output: False
Por qué: la reunión larga se traga a las otras dos
Input: meetings = [[7, 10], [2, 4], [4, 7]]
Output: True
Por qué: en orden cronológico, las reuniones solo se tocan en sus extremos
Input: meetings = []
Output: True
Por qué: caso límite: un calendario vacío no tiene nada que choque
Pistas
0 / 3
Comparar cada par de reuniones funciona, pero es cuadrático. Piensa qué pares pueden chocar de verdad una vez que las miras en un orden sensato.
Después de ordenar por hora de inicio, una reunión solo puede chocar con algo que empieza antes que ella, y la que tiene más probabilidades de seguir en curso es la inmediatamente anterior.
Ordena por hora de inicio y recorre la lista una vez. Si alguna reunión empieza antes de que termine la anterior, devuelve False. Si el recorrido termina, devuelve True.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Solución
Una vez ordenadas las reuniones por hora de inicio, la única forma de que dos se superpongan es que alguna empiece antes de que termine su predecesora inmediata: si las vecinas en ese orden nunca se superponen, sus horas de fin también están en orden, así que nada que esté más atrás puede llegar más allá de ellas. Eso convierte una pregunta sobre todos los pares en una comparación por cada par adyacente, con un menor que estricto para que las reuniones que solo se tocan pasen. El tiempo es O(n log n) por el ordenamiento (sorting), y el espacio, O(n) para la copia ordenada.
def can_attend_all(meetings):
ordered = sorted(meetings) # by start time
for prev, cur in zip(ordered, ordered[1:]):
if cur[0] < prev[1]: # starts before the last one ends
return False
return True
print(can_attend_all([[0, 30], [5, 10], [15, 20]])) # -> False
print(can_attend_all([[7, 10], [2, 4], [4, 7]])) # -> True
print(can_attend_all([])) # -> True¿Lo que te frena es la idea y no el código? Meeting Rooms lo explica.