Minimum Platforms

Q: Qual è la complessità temporale del problema delle piattaforme minime?

Ordinare i due array costa O(n log n) e la scansione successiva O(n) , quindi sono gli ordinamenti a dominare. Le copie ordinate occupano O(n) spazio aggiuntivo.

Q: In che modo minimum platforms è diverso da meeting rooms II?

Entrambi chiedono il numero massimo di intervalli che si sovrappongono in un momento. Qui un treno occupa il binario fino al minuto in cui parte; in meeting rooms II una sala è libera nel momento in cui termina la riunione. Nella scansione, questo si traduce in un solo confronto: in caso di parità, qui elabori prima l’arrivo, mentre lì elabori prima la riunione che termina.

Q: È possibile risolvere il problema delle piattaforme minime senza ordinare?

Sì, poiché ogni orario corrisponde a un orario fisso. Indicizza 2401 contatori in base al numero HHMM , aggiungi 1 a ogni arrivo e sottrai 1 a departure + 1 . La somma progressiva massima è la risposta: tempo O(n + 2400) . Indici come da 1260 a 1299 non corrispondono a orari validi e non ricevono arrivi, quindi non determinano mai un picco.

MedioOrdinamento Greedy Due puntatori

+10

Una stazione ha l'orario di un giorno: il treno i arriva a arrival[i] e parte a departure[i]. Gli orari sono numeri HHMM, ovvero l'ora senza i due punti, quindi 930 corrisponde alle 09:30.

Un treno occupa il binario dal minuto in cui arriva fino al minuto in cui parte, inclusi entrambi. Quindi un treno che arriva nel minuto in cui un altro parte non può occupare il binario di quel treno.

Restituisci il numero minimo di binari necessari alla stazione affinché nessun treno debba aspettare.

Funzione

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

arrivalinteger-array: l'orario di arrivo di ciascun treno, come numero HHMM
departureinteger-array: l'orario di partenza di ciascun treno, come numero HHMM; departure[i] corrisponde a arrival[i]
Restituisceinteger: il numero massimo di treni alla stazione nello stesso minuto, ovvero il numero minimo di binari necessari

Vincoli

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Ogni valore è un orario valido in formato HHMM: le sue ultime due cifre sono al massimo 59.
Tutti i treni circolano lo stesso giorno. Gli array non sono ordinati.

Esempi

Input: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Output: 3
Spiegazione: Alle 15:30 ci sono tre treni alla stazione: quelli dalle 15:00 alle 16:00, dalle 15:20 alle 15:35 e dalle 15:30 alle 15:45. In nessun minuto ce ne sono quattro, quindi bastano 3 binari.

Input: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Output: 2
Spiegazione: Il treno che arriva alle 12:30 incontra quello che parte alle 12:30, e lo stesso accade alle 13:00. In ognuno di quei minuti ci sono due treni alla stazione, quindi la risposta è 2, non 1.

Input: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Output: 2
Spiegazione: Il treno dalle 06:00 alle 22:00 tiene occupato un binario tutto il giorno. I treni dalle 07:00 alle 07:15 e dalle 13:00 alle 14:00 non si incontrano mai, quindi condividono un secondo binario: 2.

Per approfondire

Alcuni treni notturni arrivano prima di mezzanotte e partono dopo, quindi il numero della partenza è inferiore a quello dell’arrivo. Come conteresti i binari quando l’orario attraversa la mezzanotte?

Soluzione

La risposta è il numero massimo di treni alla stazione nello stesso minuto. Il compito consiste nel trovare il minuto più trafficato senza confrontare ogni coppia di treni. Ordina separatamente gli arrivi e le partenze; una sola scansione degli eventi della giornata, tenendo aggiornato il conteggio, permette di trovarlo in O(n log n).

Conta i treni a ogni arrivo

Corretto, ma non termina sui test più grandi

Intuizione

I treni fermi nello stesso minuto hanno tutti bisogno di binari diversi, quindi il minuto più affollato è un limite inferiore. È anche sufficiente: apri un nuovo binario solo quando un treno in arrivo trova tutti quelli aperti occupati. In quel minuto c'è un treno su ciascun binario aperto, più quello nuovo, quindi non apri mai più binari del numero massimo necessario.

Il numero di treni presenti aumenta solo quando arriva un treno, quindi il minuto più affollato è il minuto di arrivo di un treno. Per ogni treno i, conta i treni j per cui arrival[j] ≤ arrival[i] ≤ departure[j]. Entrambi i confronti usano ≤ perché un treno occupa ancora il suo binario nel minuto in cui parte.

Ognuno degli n treni controlla tutti gli n, quindi il lavoro è O(n²): 25 milioni di controlli di coppie per 5000 treni.

Algoritmo

Imposta most = 0.
Per ogni treno i, conta i treni j tali che arrival[j] ≤ arrival[i] ≤ departure[j].
Se quel conteggio è maggiore di most, memorizzalo.
Restituisci 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

Ordina entrambe le liste e scorri con due puntatori

Intuizione

Il numero di treni presenti dipende solo da quanti sono arrivati e da quanti sono partiti entro un determinato minuto, non da quale treno parte quando. Quindi ordina gli orari di arrivo e quelli di partenza come due elenchi indipendenti. Letti insieme in ordine cronologico, rappresentano gli eventi della giornata: un arrivo aggiunge un treno, una partenza ne rimuove uno.

In caso di parità, l’arrivo viene prima, perché in quel minuto il treno in partenza occupa ancora il binario. Nel primo esempio, il conteggio torna a 0 dopo la partenza delle 1100; poi gli arrivi delle 1500, 1520 e 1530 avvengono tutti prima della partenza delle 1535, quindi il conteggio raggiunge 3.

Quando gli arrivi finiscono, le partenze rimanenti possono solo diminuire il conteggio, quindi la scansione si ferma lì. L’ordinamento ha un costo di O(n log n) e la scansione richiede al massimo 2n passaggi.

Algoritmo

Ordina una copia di arrival e una copia di departure.
Imposta platforms, most, i e j su 0.
Mentre i < n: se arrivals[i] ≤ departures[j], aggiungi 1 a platforms, aggiorna most e incrementa i.
Altrimenti sottrai 1 da platforms e incrementa j.
Restituisci 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

Trappole e casi limite

Confrontare con < quando la regola inclusiva richiede ≤. Nel secondo esempio, ogni treno in arrivo occupa quindi il binario del treno che parte in quel minuto e la risposta scende da 2 a 1.
Sottrarre numeri HHMM: 1300 meno 1259 fa 41, anche se gli orari sono distanti un minuto. Confrontarli è sicuro e la soluzione esegue solo confronti.
Ordinare i treni per orario di arrivo e confrontare ciascuno solo con il treno che lo precede. Una lunga sosta come quella dalle 06:00 alle 22:00 nel terzo esempio si sovrappone a treni molto più avanti nell'elenco.
Saltare i treni che arrivano e partono nello stesso minuto. Quattro treni che sostano ciascuno dalle 10:00 alle 10:00 hanno bisogno di quattro binari.

Domande frequenti3

Qual è la complessità temporale del problema delle piattaforme minime?

Ordinare i due array costa O(n log n) e la scansione successiva O(n), quindi sono gli ordinamenti a dominare. Le copie ordinate occupano O(n) spazio aggiuntivo.

In che modo minimum platforms è diverso da meeting rooms II?

Entrambi chiedono il numero massimo di intervalli che si sovrappongono in un momento. Qui un treno occupa il binario fino al minuto in cui parte; in meeting rooms II una sala è libera nel momento in cui termina la riunione. Nella scansione, questo si traduce in un solo confronto: in caso di parità, qui elabori prima l’arrivo, mentre lì elabori prima la riunione che termina.

È possibile risolvere il problema delle piattaforme minime senza ordinare?

Sì, poiché ogni orario corrisponde a un orario fisso. Indicizza 2401 contatori in base al numero HHMM, aggiungi 1 a ogni arrivo e sottrai 1 a departure + 1. La somma progressiva massima è la risposta: tempo O(n + 2400). Indici come da 1260 a 1299 non corrispondono a orari validi e non ricevono arrivi, quindi non determinano mai un picco.

def minimumPlatforms(arrival, departure):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso