Minimum Platforms

Q: Qual é a complexidade de tempo do problema do número mínimo de plataformas?

Ordenar os dois arrays custa O(n log n) e a varredura depois disso custa O(n) , então as ordenações predominam. As cópias ordenadas ocupam O(n) de espaço extra.

Q: Em que o problema de plataformas mínimas difere do problema Meeting Rooms II?

Ambos pedem o maior número de intervalos que se sobrepõem em um mesmo instante. Aqui, um trem ocupa sua plataforma até o minuto em que parte; em Meeting Rooms II, uma sala fica livre no momento em que sua reunião termina. Na varredura, isso é uma comparação: em caso de empate, aqui você processa primeiro a chegada e, lá, a reunião que termina.

Q: É possível resolver o problema de plataformas mínimas sem ordenar?

Sim, pois todos os horários se encaixam em um relógio fixo. Indexe 2401 contadores pelo número HHMM , some 1 a cada chegada e subtraia 1 em departure + 1 . A maior soma acumulada é a resposta: tempo O(n + 2400) . Índices como 1260 a 1299 não são horários válidos e não recebem nenhuma chegada, então nunca definem um pico.

MédioOrdenação Guloso Dois ponteiros

+10

Uma estação tem a tabela de horários de um dia: o trem i chega em arrival[i] e parte em departure[i]. Os horários são números no formato HHMM, ou seja, a hora sem os dois-pontos; portanto, 930 corresponde a 09:30.

Um trem ocupa sua plataforma desde o minuto em que chega até o minuto em que parte, inclusive. Portanto, um trem que chega no mesmo minuto em que outro parte não pode usar a plataforma desse trem.

Retorne o menor número de plataformas de que a estação precisa para que nenhum trem tenha que esperar.

Função

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

arrivalinteger-array: o horário de chegada de cada trem, como um número HHMM
departureinteger-array: o horário de partida de cada trem, como um número HHMM; departure[i] corresponde a arrival[i]
Retornainteger: o maior número de trens na estação no mesmo minuto, que é o número mínimo de plataformas necessárias

Restrições

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Cada horário é um horário válido no formato HHMM: seus dois últimos dígitos são, no máximo, 59.
Todos os trens circulam no mesmo dia. Os arrays não estão ordenados.

Exemplos

Entrada: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Saída: 3
Explicação: Às 15:30, três trens estão na estação: os das 15:00 às 16:00, das 15:20 às 15:35 e das 15:30 às 15:45. Nenhum minuto tem quatro trens, então 3 plataformas são suficientes.

Entrada: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Saída: 2
Explicação: O trem que chega às 12:30 encontra o que parte às 12:30, e o mesmo acontece às 13:00. Em cada um desses minutos, há dois trens na estação, então a resposta é 2, não 1.

Entrada: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Saída: 2
Explicação: O trem das 06:00 às 22:00 mantém uma plataforma ocupada o dia todo. Os trens das 07:00 às 07:15 e das 13:00 às 14:00 nunca se encontram, então compartilham uma segunda plataforma: 2.

Para ir além

Alguns trens noturnos chegam antes da meia-noite e partem depois dela, então o horário de partida é menor que o de chegada. Como você contaria as plataformas quando os horários atravessam a meia-noite?

Solução

A resposta é o maior número de trens na estação no mesmo minuto. O trabalho consiste em encontrar esse minuto de maior movimento sem comparar cada par de trens. Ordene as chegadas e as partidas separadamente, e uma única passagem pelos eventos do dia, mantendo uma contagem acumulada, encontra esse minuto em O(n log n).

Conte os trens em cada chegada

Correta, mas não termina nos maiores testes

Intuição

Trens que param no mesmo minuto precisam de plataformas diferentes, então o minuto mais movimentado é um limite inferior. Ele também é suficiente: abra uma nova plataforma apenas quando um trem que chega encontra todas as plataformas abertas ocupadas. Nesse minuto, há um trem em cada plataforma aberta, além da nova, então você nunca abre mais plataformas do que o pico.

A quantidade de trens presentes só aumenta quando um trem chega, então o minuto mais movimentado é o minuto de chegada de algum trem. Para cada trem i, conte os trens j com arrival[j] ≤ arrival[i] ≤ departure[j]. Ambas as comparações usam ≤ porque um trem ainda ocupa sua plataforma no minuto em que parte.

Cada um dos n trens verifica todos os n, então o trabalho é O(n²): 25 milhões de verificações de pares para 5000 trens.

Algoritmo

Defina most = 0.
Para cada trem i, conte os trens j com arrival[j] ≤ arrival[i] ≤ departure[j].
Se essa contagem for maior que most, armazene-a.
Retorne 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

Ordene ambas as listas e percorra-as com dois ponteiros

Intuição

O número de trens presentes depende apenas de quantos chegaram e de quantos partiram até determinado minuto, não de qual trem parte em que momento. Portanto, ordene os horários de chegada e os horários de partida como duas listas independentes. Lidos juntos em ordem cronológica, eles são os eventos do dia: uma chegada adiciona um trem, uma partida remove um.

Em caso de empate, a chegada vem primeiro, porque o trem que está partindo ainda ocupa sua plataforma naquele minuto. No primeiro exemplo, a contagem volta a 0 após a partida às 1100; em seguida, as chegadas às 1500, 1520 e 1530 ocorrem todas antes da partida às 1535, então a contagem chega a 3.

Quando as chegadas acabam, as partidas restantes só podem reduzir a contagem, então o percurso termina nesse ponto. A ordenação custa O(n log n), e o percurso leva no máximo 2n etapas.

Algoritmo

Ordene uma cópia de arrival e uma cópia de departure.
Defina platforms, most, i e j como 0.
Enquanto i < n: se arrivals[i] ≤ departures[j], adicione 1 a platforms, atualize most e avance i.
Caso contrário, subtraia 1 de platforms e avance j.
Retorne 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

Armadilhas e casos extremos

Comparar usando < quando a regra inclusiva exige ≤. No segundo exemplo, cada trem que chega então ocupa a plataforma do trem que parte naquele minuto, e a resposta cai de 2 para 1.
Subtrair números HHMM: 1300 menos 1259 é 41, embora os horários estejam separados por um minuto. Compará-los é seguro, e a solução apenas os compara.
Ordenar os trens por horário de chegada e comparar cada um apenas com o trem anterior. Uma permanência longa, como das 06:00 às 22:00 no terceiro exemplo, se sobrepõe a trens bem mais adiante na lista.
Ignorar trens que chegam e partem no mesmo minuto. Quatro trens que ficam das 10:00 às 10:00 precisam de quatro plataformas.

Perguntas frequentes3

Qual é a complexidade de tempo do problema do número mínimo de plataformas?

Ordenar os dois arrays custa O(n log n) e a varredura depois disso custa O(n), então as ordenações predominam. As cópias ordenadas ocupam O(n) de espaço extra.

Em que o problema de plataformas mínimas difere do problema Meeting Rooms II?

Ambos pedem o maior número de intervalos que se sobrepõem em um mesmo instante. Aqui, um trem ocupa sua plataforma até o minuto em que parte; em Meeting Rooms II, uma sala fica livre no momento em que sua reunião termina. Na varredura, isso é uma comparação: em caso de empate, aqui você processa primeiro a chegada e, lá, a reunião que termina.

É possível resolver o problema de plataformas mínimas sem ordenar?

Sim, pois todos os horários se encaixam em um relógio fixo. Indexe 2401 contadores pelo número HHMM, some 1 a cada chegada e subtraia 1 em departure + 1. A maior soma acumulada é a resposta: tempo O(n + 2400). Índices como 1260 a 1299 não são horários válidos e não recebem nenhuma chegada, então nunca definem um pico.

def minimumPlatforms(arrival, departure):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada