Meeting Rooms II

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

Ambas soluciones rápidas se ejecutan en O(n log n) . La versión con montículo ordena las reuniones y realiza una operación de montículo O(log n) por reunión; la versión con dos listas realiza dos ordenamientos y un recorrido de O(n) . Ambas usan O(n) de espacio adicional. Contar las reuniones en curso en cada inicio tiene una complejidad de O(n²) .

MedioIntervalos Montículo Ordenación

+10

Recibes una lista de reuniones en dos arreglos: la reunión i transcurre desde starts[i] hasta ends[i]. En una sala se celebra una reunión a la vez, y una reunión puede comenzar en una sala justo en el momento en que termina otra reunión allí.

Escribe una función llamada minMeetingRooms que devuelva el menor número de salas que puede albergar todas las reuniones.

Función

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

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
Devuelveinteger: la menor cantidad de salas que puedan albergar todas las reuniones

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 = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Salida: 3
Explicación: A la hora 4, las reuniones de 1 a 5, de 2 a 6 y de 4 a 8 están todas en curso, así que necesitas al menos 3 salas. Tres son suficientes: la reunión de 7 a 9 ocupa la sala que queda libre a las 5.

Entrada: starts = [0, 2, 3]ends = [10, 3, 5]
Salida: 2
Explicación: La reunión de 0 a 10 mantiene una sala ocupada todo el tiempo. La reunión de 2 a 3 necesita una segunda sala, y la reunión de 3 a 5 ocupa esa misma sala cuando queda libre, así que bastan 2 salas.

+17 pruebas ocultas al enviar

Para ir más allá

¿También puedes indicar a qué sala va cada reunión, usando como máximo tantas salas como la respuesta?

Solución

El número de salas que necesitas es el mayor número de reuniones que se celebran al mismo tiempo. Contar las reuniones en curso en cada hora de inicio permite encontrarlo en O(n²). Ordenar convierte la pregunta en un recorrido por el día: un montículo mínimo con las horas en que las salas quedan libres, o dos listas ordenadas de horas de inicio y fin, da la respuesta en O(n log n).

Cuenta las reuniones que se están realizando en cada hora de inicio

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

Intuición

En cualquier momento, cada reunión que está en curso necesita una sala propia. Por lo tanto, necesitas al menos tantas salas como el mayor número de reuniones que se celebran a la vez. Esa cantidad también es suficiente: asigna las salas en orden de hora de inicio y solo se abre una sala nueva cuando todas están ocupadas, lo que significa que justo entonces se están celebrando ese número de reuniones.

El número de reuniones en curso solo aumenta cuando empieza una reunión, así que el momento de mayor actividad es el inicio de alguna reunión. Para cada reunión i, cuenta las reuniones j que cumplen starts[j] ≤ starts[i] < ends[j]: ya han empezado y todavía no han terminado. Una reunión que termina exactamente en starts[i] no se cuenta, porque su sala vuelve a estar libre en ese momento.

En el primer ejemplo, en el momento 4 están en curso las reuniones de 1 a 5, de 2 a 6 y de 4 a 8: 3. En el momento 7, solo están en curso las reuniones de 4 a 8 y de 7 a 9: 2. El mayor recuento es 3.

Cada una de las n reuniones recorre las n reuniones. Con n = 5000, eso supone 25 millones de comprobaciones: una fracción de segundo en C, varios segundos en Python o R, y cuatro veces más cada vez que n se duplica.

Algoritmo

Para cada reunión i, establece running en 0.
Para cada reunión j, suma 1 a running cuando starts[j] ≤ starts[i] < ends[j].
Conserva el mayor valor de running que hayas visto.
Devuelve ese mayor valor.

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

Montículo mínimo de las horas en que las salas quedan libres

Intuición

Asigna las salas como lo haría una persona en la recepción. Toma las reuniones en orden de hora de inicio. Para cada una, mira la sala que queda libre primero. Si está libre cuando empieza la reunión, esta recibe esa sala. Si no, todas las salas siguen ocupadas, así que abres una nueva.

Es seguro comprobar solo esa sala. Si la sala que queda libre primero sigue ocupada, todas lo están. Si está libre, cualquier sala libre es igual de buena que otra: las reuniones que aún están por celebrarse empiezan a esta hora o más tarde, así que todas las salas que están libres ahora seguirán libres para todas ellas.

Necesitas la hora de disponibilidad más temprana entre las salas, y cambia después de cada reunión. Un min-heap guarda una hora de finalización por sala y te da la menor. Al reutilizar una sala, reemplazas su hora de finalización por la hora de finalización de la nueva reunión; al abrir una sala, insertas una nueva hora de finalización. En el primer ejemplo, ordenadas por hora de inicio: de 1 a 5 da [5], de 2 a 6 da [5, 6], de 4 a 8 da [5, 6, 8], y de 7 a 9 encuentra que 5 es menor o igual que 7 y la reemplaza, dejando [6, 8, 9]. Tres salas.

Ordenar cuesta O(n log n) y cada reunión realiza una operación del heap de O(log n). heapq de Python, PriorityQueue de Java, priority_queue de C++ con greater, BinaryHeap de Rust con Reverse, container/heap de Go y SplMinHeap de PHP te proporcionan el heap. En los demás lenguajes lo mantienes en un array: el padre del índice i está en (i-1)/2, y un valor sube mientras sea menor que su padre.

Algoritmo

Ordena las reuniones por hora de inicio, conservando cada inicio junto con su propio final.
Para cada reunión, si el montículo no está vacío y su final más pequeño es anterior o igual al inicio de la reunión, reemplaza ese final por el final de la reunión.
De lo contrario, agrega el final de la reunión: se abre una nueva sala.
Devuelve el tamaño del montículo, una entrada por sala.

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)

Ordena los inicios y los finales por separado

Intuición

El montón recuerda qué hora de finalización corresponde a cada sala, pero la respuesta es solo un recuento. Cuando empieza una reunión, lo único que importa es si alguna reunión ha terminado para entonces y ha dejado una sala libre; no importa cuál haya sido. Así que ordena los inicios y los finales en dos listas separadas y recorre los inicios con un puntero ended en la lista de finales.

Para cada inicio, en orden: si es igual o posterior a endTimes[ended], una reunión ya ha terminado. Su sala pasa a la nueva reunión y ended avanza. De lo contrario, todas las salas en uso siguen ocupadas y rooms aumenta en uno. Cada inicio consume como máximo un final, del mismo modo que una sala reutilizada en el montón intercambia un final antiguo por uno nuevo.

En el primer ejemplo, los inicios son 1, 2, 4, 7 y los finales, 5, 6, 8, 9. Los inicios 1, 2 y 4 ocurren todos antes del final 5, así que rooms aumenta hasta 3. El inicio 7 es igual o posterior a 5, así que reutiliza esa sala y ended avanza hasta el final 6. La respuesta es 3. El ≥ es lo que permite que las reuniones consecutivas compartan una sala: en el segundo ejemplo, el inicio 12 coincide con el final 12 y reutiliza esa sala.

El recuento nunca supera el pico real: cuando rooms aumenta, el siguiente final todavía está en el futuro, así que en ese momento hay rooms reuniones en curso. También alcanza el pico, porque un inicio solo evita abrir una sala cuando un final real, igual o anterior, ha liberado una. Las dos ordenaciones cuestan O(n log n), el recorrido cuesta O(n) y las copias ordenadas ocupan O(n) de espacio.

Algoritmo

Ordena una copia de los inicios y una copia de los finales.
Establece rooms y ended en 0.
Para cada inicio, en orden, si es igual o posterior a endTimes[ended], suma 1 a ended: la reunión ocupa una sala liberada.
De lo contrario, suma 1 a rooms.
Devuelve 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

Errores comunes y casos límite

La mayoría de los errores están en la comparación cuando una reunión termina justo cuando empieza otra o en qué sala se comprueba.

Comprobar start > end en lugar de start ≥ end. Entonces una reunión no puede usar una sala justo cuando queda libre, y las reuniones de 10 a 12, de 12 a 14 y de 14 a 16 necesitan 2 salas en lugar de 1.
Comprobar la sala que abriste al final en lugar de la sala que queda libre primero. Para las reuniones de 1 a 3, de 2 a 10 y de 4 a 6, la última sala abierta está ocupada hasta las 10, así que abres una tercera sala mientras la primera está libre desde las 3.
Tomar la mayor cantidad de reuniones que se superponen con una reunión y sumarle uno. La reunión de 0 a 10 se superpone con las reuniones de 2 a 3 y de 3 a 5, pero esas dos no se superponen entre sí, así que 2 salas son suficientes, no 3.
Confundir los dos enfoques de ordenamiento. En el enfoque del montículo, cada hora de finalización debe ir emparejada con su propia hora de inicio antes de ordenar por hora de inicio; el enfoque de las dos listas ordena por separado las horas de inicio y las de finalización a propósito.

Preguntas frecuentes4

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

Ambas soluciones rápidas se ejecutan en O(n log n). La versión con montículo ordena las reuniones y realiza una operación de montículo O(log n) por reunión; la versión con dos listas realiza dos ordenamientos y un recorrido de O(n). Ambas usan O(n) de espacio adicional. Contar las reuniones en curso en cada inicio tiene una complejidad de O(n²).

¿Por qué un montículo mínimo resuelve Meeting Rooms II?

Al tomar las reuniones en orden de inicio, la única sala que vale la pena comprobar es la que queda libre primero. Un montículo mínimo de horas de finalización te da esa sala en O(1) y se actualiza en O(log n). El montículo solo crece cuando todas las salas están ocupadas, así que su tamaño final es el menor número de salas necesarias.

¿Se puede resolver Can Meeting Rooms II sin un montículo?

Sí. Ordena las horas de inicio y las horas de finalización como dos listas separadas y recorre los inicios con un puntero hacia las finalizaciones. Un inicio que sea igual o posterior a la siguiente finalización sin usar reutiliza una sala; cualquier otro inicio abre una. La misma idea funciona como una línea de barrido: convierte cada reunión en un evento de +1 al inicio y uno de -1 al final, procesa las finalizaciones antes que los inicios cuando coinciden las horas y lleva un registro del mayor total acumulado.

¿La respuesta es la misma que la cantidad máxima de reuniones que se superponen al mismo tiempo?

Sí. Las reuniones que se llevan a cabo al mismo tiempo necesitan salas diferentes, así que necesitas al menos esa cantidad. Asignar a cada reunión, en orden de inicio, cualquier sala que esté libre nunca requiere más, así que el número máximo de reuniones simultáneas es exactamente la respuesta.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Meeting Rooms II

Función

Restricciones

Ejemplos

Pistas

Solución

Cuenta las reuniones que se están realizando en cada hora de inicio

Montículo mínimo de las horas en que las salas quedan libres

Ordena los inicios y los finales por separado

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares