Meeting Rooms II

Q: Qual é a complexidade de tempo de Meeting Rooms II?

As duas soluções rápidas têm complexidade O(n log n) . A versão com heap ordena as reuniões e realiza uma operação de heap O(log n) por reunião; a versão com duas listas faz duas ordenações e uma varredura O(n) . Ambas usam espaço extra O(n) . Contar as reuniões em andamento em cada início tem complexidade O(n²) .

MédioIntervalos Heap Ordenação

+10

Você recebe uma lista de reuniões como dois arrays: a reunião i vai de starts[i] a ends[i]. Uma sala comporta uma reunião por vez, e uma reunião pode começar em uma sala exatamente no momento em que outra reunião termina nela.

Escreva uma função chamada minMeetingRooms que retorne o menor número de salas capaz de comportar todas as reuniões.

Função

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

startsinteger-array: o horário de início de cada reunião
endsinteger-array: o horário de término de cada reunião, no mesmo índice que seu horário de início
Retornainteger: o menor número de salas que pode acomodar todas as reuniões

Restrições

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
As reuniões não estão ordenadas. Duas reuniões podem ser idênticas.

Exemplos

Entrada: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Saída: 3
Explicação: No instante 4, as reuniões de 1 a 5, de 2 a 6 e de 4 a 8 estão todas acontecendo, então você precisa de pelo menos 3 salas. Três são suficientes: a reunião de 7 a 9 ocupa a sala que fica livre às 5.

Entrada: starts = [0, 2, 3]ends = [10, 3, 5]
Saída: 2
Explicação: A reunião das 0 às 10 mantém uma sala ocupada o tempo todo. A reunião das 2 às 3 precisa de uma segunda sala, e a reunião das 3 às 5 usa essa mesma sala assim que ela fica livre, então 2 salas são suficientes.

+17 testes ocultos ao enviar

Para ir além

Você também pode dizer em qual sala cada reunião acontece, sem usar mais salas do que a resposta indica?

Solução

O número de salas de que você precisa é o maior número de reuniões acontecendo ao mesmo tempo. Contar as reuniões em andamento a cada horário de início encontra esse número em O(n²). A ordenação transforma a questão em uma única passagem pelo dia: um min-heap com os horários em que as salas ficam livres, ou duas listas ordenadas de horários de início e término, fornece a resposta em O(n log n).

Conte as reuniões em andamento em cada início

Correta, mas não termina nos maiores testes

Intuição

A qualquer momento, cada reunião em andamento precisa de uma sala própria. Portanto, você precisa de pelo menos tantas salas quanto o maior número de reuniões acontecendo ao mesmo tempo. Essa quantidade também é suficiente: distribua as salas em ordem de horário de início, e uma nova sala só será aberta quando todas estiverem ocupadas, o que significa que esse número de reuniões está acontecendo naquele instante.

O número de reuniões em andamento só aumenta quando uma reunião começa, então o momento mais movimentado é o início de alguma reunião. Para cada reunião i, conte as reuniões j para as quais starts[j] ≤ starts[i] < ends[j]: elas já começaram e ainda não terminaram. Uma reunião que termina exatamente em starts[i] não é contada, porque sua sala fica livre novamente naquele instante.

No primeiro exemplo, no instante 4, estão acontecendo as reuniões de 1 a 5, de 2 a 6 e de 4 a 8: 3. No instante 7, estão acontecendo apenas as reuniões de 4 a 8 e de 7 a 9: 2. A maior contagem é 3.

Cada uma das n reuniões percorre todas as n reuniões. Com n = 5000, isso representa 25 milhões de verificações: uma fração de segundo em C, vários segundos em Python ou R, e quatro vezes mais a cada vez que n dobra.

Algoritmo

Para cada reunião i, defina running como 0.
Para cada reunião j, adicione 1 a running quando starts[j] ≤ starts[i] < ends[j].
Mantenha o maior valor de running que você tiver visto.
Retorne esse maior 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

Min-heap dos horários em que as salas ficam livres

Intuição

Aloque as salas como uma pessoa na recepção faria. Considere as reuniões na ordem do horário de início. Para cada uma, veja a sala que fica livre primeiro. Se ela estiver livre até o horário de início da reunião, a reunião fica com essa sala. Caso contrário, todas as salas ainda estão ocupadas, então você abre uma nova.

É seguro verificar apenas essa sala. Se a sala que fica livre primeiro ainda estiver ocupada, todas as outras também estarão. Se ela estiver livre, qualquer sala livre serve: as reuniões que ainda vão acontecer começam nesse horário ou depois, então todas as salas que estão livres agora continuarão livres para elas.

Você precisa do horário mais cedo em que uma sala fica livre, e ele muda após cada reunião. Um min-heap mantém um horário de término por sala e fornece o menor deles. Reutilizar uma sala substitui seu horário de término pelo horário de término da nova reunião; abrir uma sala adiciona um novo horário de término. No primeiro exemplo, em ordem de início: 1 a 5 resulta em [5], 2 a 6 resulta em [5, 6], 4 a 8 resulta em [5, 6, 8], e 7 a 9 encontra 5 igual ou anterior a 7 e o substitui, deixando [6, 8, 9]. Três salas.

A ordenação custa O(n log n) e cada reunião realiza uma operação no heap de O(log n). heapq do Python, PriorityQueue do Java, priority_queue com greater do C++, BinaryHeap com Reverse do Rust, container/heap do Go e SplMinHeap do PHP fornecem o heap. Nas outras linguagens, você o mantém em um array: o pai do índice i fica em (i-1)/2, e um valor sobe enquanto for menor que seu pai.

Algoritmo

Ordene as reuniões pelo horário de início, mantendo cada horário de início associado ao seu próprio horário de término.
Para cada reunião, se o heap não estiver vazio e o menor horário de término for igual ou anterior ao horário de início da reunião, substitua esse horário de término pelo horário de término da reunião.
Caso contrário, insira o horário de término da reunião: uma nova sala é aberta.
Retorne o tamanho do heap, com uma 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)

Classifique os horários de início e término separadamente

Intuição

O heap memoriza qual horário de término pertence a qual sala, mas a resposta é apenas uma contagem. Quando uma reunião começa, só importa se alguma reunião já terminou e liberou uma sala; qual reunião foi não importa. Então, ordene os horários de início e de término em duas listas separadas e percorra os horários de início, com um ponteiro ended na lista de horários de término.

Para cada horário de início, em ordem: se ele for igual ou posterior a endTimes[ended], uma reunião já terminou. A sala dela recebe a nova reunião, e ended avança. Caso contrário, todas as salas em uso ainda estão ocupadas, e rooms aumenta em um. Cada horário de início consome no máximo um horário de término, assim como uma sala reutilizada no heap troca um horário de término antigo por um novo.

No primeiro exemplo, os horários de início são 1, 2, 4, 7 e os de término são 5, 6, 8, 9. Os horários de início 1, 2 e 4 ocorrem antes do horário de término 5, então rooms chega a 3. O horário de início 7 é igual ou posterior a 5, então reutiliza essa sala e ended avança para o horário de término 6. A resposta é 3. O ≥ é o que permite que reuniões consecutivas compartilhem uma sala: no segundo exemplo, o horário de início 12 coincide com o horário de término 12 e reutiliza essa sala.

A contagem nunca ultrapassa o pico real: quando rooms aumenta, o próximo horário de término ainda está no futuro, então todas as reuniões rooms estão acontecendo naquele momento. A contagem também chega ao pico, porque um horário de início só evita abrir uma sala quando um horário de término real, igual ou anterior a ele, liberou uma. Duas ordenações custam O(n log n), a varredura O(n), e as cópias ordenadas ocupam O(n) de espaço.

Algoritmo

Ordene uma cópia dos horários de início e uma cópia dos horários de término.
Defina rooms e ended como 0.
Para cada horário de início, em ordem, se ele for igual ou posterior a endTimes[ended], some 1 a ended: a reunião ocupa uma sala liberada.
Caso contrário, some 1 a rooms.
Retorne 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

Armadilhas e casos extremos

A maioria dos bugs está na comparação em um momento de contato ou em qual sala é verificada.

Verificar start > end em vez de start ≥ end. Assim, uma reunião não pode usar uma sala no momento em que ela fica livre, e as reuniões das 10 às 12, das 12 às 14 e das 14 às 16 ocupam 2 salas em vez de 1.
Verificar a sala que você abriu por último em vez da sala que fica livre primeiro. Para as reuniões das 1 às 3, das 2 às 10 e das 4 às 6, a última sala aberta fica ocupada até as 10, então você abre uma terceira sala, enquanto a primeira está livre desde as 3.
Usar o maior número de reuniões que se sobrepõem a uma reunião, mais um. A reunião das 0 às 10 se sobrepõe às reuniões das 2 às 3 e das 3 às 5, mas essas duas não se sobrepõem entre si, então 2 salas são suficientes, não 3.
Confundir as duas abordagens de ordenação. O heap precisa que cada horário de término esteja associado ao seu próprio horário de início antes da ordenação pelos horários de início; a abordagem de duas listas ordena os horários de início e os horários de término separadamente de propósito.

Perguntas frequentes4

Qual é a complexidade de tempo de Meeting Rooms II?

As duas soluções rápidas têm complexidade O(n log n). A versão com heap ordena as reuniões e realiza uma operação de heap O(log n) por reunião; a versão com duas listas faz duas ordenações e uma varredura O(n). Ambas usam espaço extra O(n). Contar as reuniões em andamento em cada início tem complexidade O(n²).

Por que um min-heap resolve o problema Meeting Rooms II?

Considerando as reuniões na ordem de início, a única sala que vale a pena verificar é a que fica livre primeiro. Um min-heap de horários de término fornece essa sala em O(1) e é atualizado em O(log n). O heap só cresce quando todas as salas estão ocupadas, então seu tamanho final é o menor número de salas necessário.

É possível resolver Meeting Rooms II sem um heap?

Sim. Ordene os horários de início e os horários de término em duas listas separadas e percorra os horários de início com um ponteiro para os horários de término. Um início no mesmo horário ou após o próximo término ainda não usado reutiliza uma sala; qualquer outro início abre uma sala. A mesma ideia funciona como uma linha de varredura: transforme cada reunião em um evento +1 no início e um evento -1 no término, processe os términos antes dos inícios em horários iguais e acompanhe o maior total acumulado.

A resposta é igual ao maior número de reuniões que se sobrepõem em um mesmo momento?

Sim. Reuniões que acontecem ao mesmo tempo precisam de salas diferentes, então você precisa de pelo menos esse número de salas. Atribuir a cada reunião, na ordem de início, qualquer sala que esteja livre nunca exige mais salas, então o número máximo de reuniões simultâneas é exatamente a resposta.

Python

def minMeetingRooms(starts, ends):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Meeting Rooms II

Função

Restrições

Exemplos

Dicas

Solução

Conte as reuniões em andamento em cada início

Min-heap dos horários em que as salas ficam livres

Classifique os horários de início e término separadamente

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos