Minimum Platforms

Q: ¿Cuál es la complejidad temporal del problema de las plataformas mínimas?

Ordenar los dos arreglos cuesta O(n log n) y el recorrido posterior cuesta O(n) , así que predominan las ordenaciones. Las copias ordenadas ocupan O(n) de espacio adicional.

Q: ¿En qué se diferencia el problema del número mínimo de andenes del de Meeting Rooms II?

Ambos preguntan por el máximo número de intervalos que se solapan en un mismo momento. Aquí, un tren ocupa su andén durante el minuto en que sale; en Meeting Rooms II, una sala queda libre en el momento en que termina su reunión. En el barrido, eso se reduce a una comparación: en caso de empate, aquí procesas primero la llegada y allí, la reunión que termina.

Q: ¿Se puede resolver el problema de las plataformas mínimas sin ordenar?

Sí, ya que cada hora corresponde a una hora fija del reloj. Indexa 2401 contadores por el número HHMM , suma 1 en cada llegada y resta 1 en departure + 1 . La suma acumulada más alta es la respuesta: tiempo O(n + 2400) . Los índices como 1260 a 1299 no son horas del reloj y no reciben llegadas, así que nunca establecen un máximo.

MedioOrdenación Voraz Dos punteros

+10

Una estación tiene el horario de un día: el tren i llega a arrival[i] y sale a departure[i]. Las horas son números HHMM, la hora sin los dos puntos, así que 930 son las 09:30.

Un tren ocupa su andén desde el minuto en que llega hasta el minuto en que sale, ambos inclusive. Por lo tanto, un tren que llega en el mismo minuto en que sale otro no puede ocupar el andén de ese tren.

Devuelve el número mínimo de andenes que necesita la estación para que ningún tren tenga que esperar.

Función

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: la hora de llegada de cada tren, como un número HHMM
departureinteger-array: la hora de salida de cada tren, como un número HHMM; departure[i] corresponde a arrival[i]
Devuelveinteger: el mayor número de trenes en la estación en el mismo minuto, que es el menor número de andenes necesarios

Restricciones

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Cada hora es una hora válida HHMM: sus dos últimos dígitos son como máximo 59.
Todos los trenes circulan el mismo día. Los arreglos no están ordenados.

Ejemplos

Entrada: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Salida: 3
Explicación: A las 15:30 hay tres trenes en la estación: los que van de 15:00 a 16:00, de 15:20 a 15:35 y de 15:30 a 15:45. En ningún minuto hay cuatro, así que bastan 3 andenes.

Entrada: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Salida: 2
Explicación: El tren que llega a las 12:30 se encuentra con el que sale a las 12:30, y lo mismo ocurre a las 13:00. En cada uno de esos minutos hay dos trenes en la estación, así que la respuesta es 2, no 1.

Entrada: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Salida: 2
Explicación: El tren de 06:00 a 22:00 mantiene un andén ocupado todo el día. Los trenes de 07:00 a 07:15 y de 13:00 a 14:00 nunca coinciden, así que comparten un segundo andén: 2.

Para ir más allá

Algunos trenes nocturnos llegan antes de la medianoche y salen después, así que su número de salida es menor que el de llegada. ¿Cómo contarías los andenes cuando el horario cruza la medianoche?

Solución

La respuesta es el mayor número de trenes en la estación durante el mismo minuto. El trabajo consiste en encontrar ese minuto de mayor actividad sin comparar cada par de trenes. Ordena por separado las llegadas y las salidas, y un recorrido por los eventos del día llevando un conteo acumulado permite encontrarlo en O(n log n).

Cuenta los trenes en cada llegada

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

Intuición

Los trenes que están en la misma hora necesitan plataformas distintas, así que la hora de mayor afluencia es un límite inferior. También es suficiente: abre una plataforma nueva solo cuando un tren que llega encuentra todas las plataformas abiertas ocupadas. En esa hora, hay un tren en cada plataforma abierta, más el nuevo, así que nunca abrirás más plataformas que el máximo.

La cantidad de trenes presentes solo aumenta cuando llega un tren, así que la hora de mayor afluencia es la hora de llegada de algún tren. Para cada tren i, cuenta los trenes j que cumplen arrival[j] ≤ arrival[i] ≤ departure[j]. Ambas comparaciones usan ≤ porque un tren sigue en su plataforma durante la hora en que se va.

Cada uno de los n trenes comprueba los n, así que el trabajo es O(n²): 25 millones de comprobaciones de pares para 5000 trenes.

Algoritmo

Establece most = 0.
Para cada tren i, cuenta los trenes j con arrival[j] ≤ arrival[i] ≤ departure[j].
Si ese recuento es mayor que most, guárdalo.
Devuelve most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

Ordena ambas listas y recórrelas con dos punteros

Intuición

El número de trenes presentes depende únicamente de cuántos han llegado y cuántos se han ido en un minuto dado, no de qué tren se va y cuándo. Así que ordena las horas de llegada y las horas de salida como dos listas independientes. Leídas juntas en orden cronológico, son los eventos del día: una llegada añade un tren, una salida elimina uno.

En caso de empate, la llegada va primero, porque el tren que se va todavía ocupa su andén durante ese minuto. En el primer ejemplo, el recuento vuelve a 0 después de la salida de las 1100; luego, las llegadas de las 1500, 1520 y 1530 ocurren todas antes de la salida de las 1535, así que alcanza 3.

Cuando se acaban las llegadas, las salidas restantes solo pueden reducir el recuento, así que el recorrido se detiene ahí. La ordenación cuesta O(n log n) y el recorrido requiere como máximo 2n pasos.

Algoritmo

Ordena una copia de arrival y una copia de departure.
Establece platforms, most, i y j en 0.
Mientras i < n: si arrivals[i] ≤ departures[j], suma 1 a platforms, actualiza most y avanza i.
De lo contrario, resta 1 a platforms y avanza j.
Devuelve most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

Errores comunes y casos límite

Comparar usando < cuando la regla inclusiva requiere ≤. En el segundo ejemplo, cada tren que llega después ocupa el andén del tren que se va en ese minuto, y la respuesta baja de 2 a 1.
Restar números HHMM: 1300 menos 1259 es 41, aunque los horarios están separados por un minuto. Compararlos es seguro, y la solución solo los compara.
Ordenar los trenes por hora de llegada y comparar cada uno solo con el tren anterior. Una estadía larga, como de 06:00 a 22:00 en el tercer ejemplo, se superpone con trenes que están mucho más adelante en la lista.
Omitir los trenes que llegan y se van en el mismo minuto. Cuatro trenes que permanecen de 10:00 a 10:00 necesitan cuatro andenes.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del problema de las plataformas mínimas?

Ordenar los dos arreglos cuesta O(n log n) y el recorrido posterior cuesta O(n), así que predominan las ordenaciones. Las copias ordenadas ocupan O(n) de espacio adicional.

¿En qué se diferencia el problema del número mínimo de andenes del de Meeting Rooms II?

Ambos preguntan por el máximo número de intervalos que se solapan en un mismo momento. Aquí, un tren ocupa su andén durante el minuto en que sale; en Meeting Rooms II, una sala queda libre en el momento en que termina su reunión. En el barrido, eso se reduce a una comparación: en caso de empate, aquí procesas primero la llegada y allí, la reunión que termina.

¿Se puede resolver el problema de las plataformas mínimas sin ordenar?

Sí, ya que cada hora corresponde a una hora fija del reloj. Indexa 2401 contadores por el número HHMM, suma 1 en cada llegada y resta 1 en departure + 1. La suma acumulada más alta es la respuesta: tiempo O(n + 2400). Los índices como 1260 a 1299 no son horas del reloj y no reciben llegadas, así que nunca establecen un máximo.

def minimumPlatforms(arrival, departure):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

Salida Esperada