Meeting Rooms

Q: ¿Cuál es la complejidad temporal de Meeting Rooms?

Ordenar las reuniones por hora de inicio cuesta O(n log n) , y recorrerlas comparando los elementos vecinos cuesta O(n) , por lo que el total es O(n log n) . Comparar cada par en cambio cuesta O(n²) .

Q: ¿Por qué basta con comparar cada reunión con la anterior?

Después de ordenar por hora de inicio, si hasta ahora no se ha encontrado ningún conflicto, las reuniones forman una cadena en la que cada una empieza a la hora de finalización de la anterior o después. La última de la cadena es la que termina más tarde. Una reunión nueva que empieza a la hora de finalización de esta o después no puede solaparse con ninguna de las anteriores.

Q: ¿Las reuniones que se tocan cuentan como superpuestas?

No en este problema: una reunión puede empezar justo en el momento en que termina otra. Por eso la comprobación es un start < previous end estricto. Si no se permitieran reuniones consecutivas, la comprobación sería start ≤ previous end .

Q: ¿Cómo encuentras el número mínimo de salas de reuniones?

Ordena las horas de inicio y las horas de fin como dos listas separadas y luego recorre ambas: cada inicio abre una sala y cada fin que ocurre en o antes del siguiente inicio libera una. La respuesta es el mayor número de salas abiertas a la vez. Responder aquí a la pregunta de sí o no equivale a preguntar si basta con una sola sala.

FácilIntervalos Ordenación

+10

Recibes una lista de reuniones en forma de dos arreglos: la reunión i va desde starts[i] hasta ends[i]. Una persona quiere asistir a todas, así que no puede haber dos reuniones que se solapen. Una reunión puede empezar justo en el momento en que termina otra. Devuelve true si la persona puede asistir a todas las reuniones y false en caso contrario.

Función

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

startsinteger-array: la hora de inicio de cada reunión
endsinteger-array: la hora de finalización de cada reunión, en el mismo índice que su hora de inicio
Devuelveboolean: true si no se superponen dos reuniones, false en caso contrario

Restricciones

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Las reuniones no están ordenadas. Dos reuniones pueden ser idénticas.

Ejemplos

Entrada: starts = [9, 13, 10]ends = [10, 15, 12]
Salida: true
Explicación: En orden cronológico, las reuniones van de 9 a 10, de 10 a 12 y de 13 a 15. La segunda empieza justo cuando termina la primera, lo cual está permitido, así que la respuesta es true.

Entrada: starts = [1, 4, 7]ends = [5, 6, 8]
Salida: false
Explicación: La reunión de 1 a 5 sigue en curso a las 4, cuando empieza la reunión de 4 a 6, así que la respuesta es false.

+15 pruebas ocultas al enviar

Para ir más allá

Si las reuniones se reservan de una en una, ¿cómo comprobarías cada nueva reserva con el horario en O(log n), sin volver a ordenar todo?

Solución

Revisar cada par de reuniones detecta cualquier conflicto, pero cuesta O(n²). Ordenar por hora de inicio cambia la pregunta: una reunión solo puede entrar en conflicto con su vecina en el orden ordenado, así que basta con una comparación por reunión.

Compara cada par

Correcto, pero no termina con las pruebas más grandes

Intuición

Dos reuniones se solapan cuando cada una empieza antes de que termine la otra. Para las reuniones de 1 a 5 y de 4 a 6: 1 es menor que 6 y 4 es menor que 5, así que se solapan. Para las reuniones de 9 a 10 y de 10 a 12: 10 no es menor que 10, así que solo coinciden en el límite.

Usar < estricto en ambos lados permite que una reunión empiece exactamente cuando termina otra. Ejecuta la prueba con cada par y devuelve false en el primer solapamiento.

El problema es la cantidad de pares. Con n = 5000 reuniones hay unos 12,5 millones de pares, y un horario sin solapamientos te obliga a comprobarlos todos, lo cual es demasiado lento para las pruebas más grandes.

Algoritmo

Para cada índice i y cada índice j posterior:
Si starts[i] < ends[j] y starts[j] < ends[i], las dos reuniones se solapan: devuelve false.
Si ningún par se solapa, devuelve 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

Ordena por el inicio y comprueba los elementos vecinos

Intuición

Ordena las reuniones por hora de inicio, manteniendo cada inicio junto con su propio final. Ahora fíjate en cualquier reunión y en la que está justo antes. Si la anterior termina después de que empieza la siguiente, se solapan. Si no, la reunión siguiente empieza en el mismo momento o después de que termina la anterior.

¿Por qué solo tienes que comprobar la reunión vecina? Si todas las reuniones hasta el momento empiezan en el mismo momento o después de que termina la anterior, las reuniones hasta el momento nunca se solapan, y la que está justo antes es la que termina más tarde. Una nueva reunión que empieza en el mismo momento o después de que termina esta, empieza en el mismo momento o después de que terminan todas las demás.

En el primer ejemplo, las reuniones ordenadas son de 9 a 10, de 10 a 12 y de 13 a 15. El inicio 10 no es anterior al final 10, y el inicio 13 no es anterior al final 12, así que no hay solapamientos. Las horas de inicio iguales siempre se solapan, ya que cada reunión dura al menos una unidad, y la comprobación también las detecta.

La ordenación cuesta O(n log n) y el recorrido cuesta O(n). La copia de las reuniones en pares ocupa O(n) espacio.

Algoritmo

Empareja cada inicio con su final.
Ordena los pares por hora de inicio.
Para cada reunión después de la primera, compara su inicio con el final de la reunión anterior.
Si el inicio es menor, devuelve false.
Después del bucle, devuelve 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

Errores comunes y casos límite

Los errores más comunes tienen que ver con qué extremos se comparan y cómo se tratan las reuniones que se tocan.

Ordenar starts y dejar ends en el orden de entrada. Cada hora de finalización debe ir junto con su propia hora de inicio; de lo contrario, comparas una hora de inicio con la hora de finalización de otra reunión.
Usar ≤ en lugar de <. Las reuniones de 9 a 10 y de 10 a 12 se tocan, pero no se superponen, y la respuesta para ellas es true.
Comprobar únicamente que cada reunión termina antes de que empiece la siguiente, según el orden de entrada. La entrada no está ordenada, así que las reuniones contiguas en la entrada no indican nada.
Escribir la prueba de pares con una sola condición, como starts[j] < ends[i]. Solo funciona cuando la reunión j empieza más tarde; para las reuniones de 5 a 6 y de 0 a 1, en ese orden, 0 < 6 indica un conflicto que no existe.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Meeting Rooms?

Ordenar las reuniones por hora de inicio cuesta O(n log n), y recorrerlas comparando los elementos vecinos cuesta O(n), por lo que el total es O(n log n). Comparar cada par en cambio cuesta O(n²).

¿Por qué basta con comparar cada reunión con la anterior?

Después de ordenar por hora de inicio, si hasta ahora no se ha encontrado ningún conflicto, las reuniones forman una cadena en la que cada una empieza a la hora de finalización de la anterior o después. La última de la cadena es la que termina más tarde. Una reunión nueva que empieza a la hora de finalización de esta o después no puede solaparse con ninguna de las anteriores.

¿Las reuniones que se tocan cuentan como superpuestas?

No en este problema: una reunión puede empezar justo en el momento en que termina otra. Por eso la comprobación es un start < previous end estricto. Si no se permitieran reuniones consecutivas, la comprobación sería start ≤ previous end.

¿Cómo encuentras el número mínimo de salas de reuniones?

Ordena las horas de inicio y las horas de fin como dos listas separadas y luego recorre ambas: cada inicio abre una sala y cada fin que ocurre en o antes del siguiente inicio libera una. La respuesta es el mayor número de salas abiertas a la vez. Responder aquí a la pregunta de sí o no equivale a preguntar si basta con una sola sala.

Python

def canAttendMeetings(starts, ends):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado

true