Meeting Rooms

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

Ordenar as reuniões pelo horário de início custa O(n log n) , e a passagem que compara vizinhos é O(n) , então o total é O(n log n) . Comparar cada par, em vez disso, custa O(n²) .

Q: Por que basta comparar cada reunião com a anterior?

Depois de ordenar pelo horário de início, se nenhum conflito tiver sido encontrado até então, as reuniões formam uma cadeia em que cada uma começa no horário de término da anterior ou depois dele. A última reunião da cadeia termina mais tarde. Uma nova reunião que começa no horário de término dela ou depois dele não pode se sobrepor a nenhuma das reuniões anteriores.

Q: Reuniões que se tocam são consideradas sobrepostas?

Não neste problema: uma reunião pode começar exatamente no momento em que outra termina. É por isso que a verificação usa start < previous end . Se reuniões consecutivas fossem proibidas, a verificação seria start ≤ previous end .

Q: Como encontrar o número mínimo de salas de reunião?

Ordene os horários de início e os horários de término em duas listas separadas e, em seguida, percorra ambas: cada início abre uma sala, e cada término que ocorre antes ou no horário do próximo início libera uma. O maior número de salas abertas ao mesmo tempo é a resposta. Responder à pergunta de sim ou não aqui é o mesmo que perguntar se uma sala é suficiente.

FácilIntervalos Ordenação

+10

Você recebe uma lista de reuniões em dois arrays: a reunião i ocorre de starts[i] até ends[i]. Uma pessoa quer participar de todas elas, então nenhuma reunião pode se sobrepor a outra. Uma reunião pode começar exatamente no momento em que outra termina. Retorne true se a pessoa puder participar de todas as reuniões e false caso contrário.

Função

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

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
Retornaboolean: true se nenhuma das reuniões se sobrepõe, false caso contrário

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 = [9, 13, 10]ends = [10, 15, 12]
Saída: true
Explicação: Em ordem cronológica, as reuniões acontecem das 9 às 10, das 10 às 12 e das 13 às 15. A segunda começa no momento em que a primeira termina, o que é permitido, então a resposta é true.

Entrada: starts = [1, 4, 7]ends = [5, 6, 8]
Saída: false
Explicação: A reunião das 1 às 5 ainda está em andamento às 4, quando começa a reunião das 4 às 6, então a resposta é false.

+15 testes ocultos ao enviar

Para ir além

Se as reuniões forem agendadas uma de cada vez, como você verificaria cada novo agendamento em relação à agenda em O(log n), sem ordenar tudo novamente?

Solução

Verificar cada par de reuniões encontra qualquer conflito, mas isso custa O(n²). Ordenar pelo horário de início muda a questão: uma reunião só pode entrar em conflito com sua vizinha na ordem ordenada, então uma comparação por reunião é suficiente.

Compare cada par

Correta, mas não termina nos maiores testes

Intuição

Duas reuniões entram em conflito quando cada uma começa antes de a outra terminar. Para reuniões das 1 às 5 e das 4 às 6: 1 é antes de 6 e 4 é antes de 5, então elas entram em conflito. Para reuniões das 9 às 10 e das 10 às 12: 10 não é antes de 10, então elas apenas se encostam.

Usar < estrito nos dois lados é o que permite que uma reunião comece exatamente quando outra termina. Execute o teste em cada par e retorne false no primeiro conflito.

O problema é o número de pares. Com n = 5000 reuniões, há cerca de 12,5 milhões de pares, e uma agenda sem conflitos obriga você a verificar todos eles, o que é lento demais para os maiores testes.

Algoritmo

Para cada índice i e cada índice j posterior a ele:
Se starts[i] < ends[j] e starts[j] < ends[i], as duas reuniões se sobrepõem: retorne false.
Se nenhum par se sobrepuser, retorne true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Ordene pelo início e verifique os vizinhos

Intuição

Ordene as reuniões pelo horário de início, mantendo cada início junto com seu próprio fim. Agora observe qualquer reunião e a que vem imediatamente antes dela. Se a reunião anterior termina depois do início da seguinte, elas entram em conflito. Caso contrário, a reunião seguinte começa no momento em que a anterior termina ou depois dele.

Por que basta verificar a reunião vizinha? Se todas as reuniões até agora começam no momento em que a reunião anterior termina ou depois dele, então elas nunca se sobrepõem, e a reunião imediatamente anterior é a que termina mais tarde. Uma nova reunião que começa no momento em que ela termina ou depois dele começa no momento em que todas elas terminam ou depois disso.

No primeiro exemplo, as reuniões ordenadas são das 9 às 10, das 10 às 12 e das 13 às 15. O início 10 não é anterior ao fim 10, e o início 13 não é anterior ao fim 12, então não há conflito. Horários de início iguais sempre entram em conflito, pois toda reunião dura pelo menos uma unidade, e a verificação também os detecta.

A ordenação custa O(n log n) e a passagem custa O(n). A cópia das reuniões em pares ocupa O(n) de espaço.

Algoritmo

Emparelhe cada início com seu fim.
Ordene os pares pelo horário de início.
Para cada reunião após a primeira, compare seu início com o fim da reunião anterior.
Se o início for menor, retorne false.
Após o loop, retorne true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Armadilhas e casos extremos

Os erros mais comuns estão relacionados a quais extremidades são comparadas e a como reuniões consecutivas são tratadas.

Ordenar starts e deixar ends na ordem de entrada. Cada horário de término precisa acompanhar seu próprio horário de início; caso contrário, você compara o horário de início de uma reunião com o horário de término de outra.
Usar ≤ em vez de <. Reuniões das 9 às 10 e das 10 às 12 são consecutivas, mas não se sobrepõem, e a resposta para elas é true.
Verificar apenas se cada reunião termina antes de a próxima começar, seguindo a ordem de entrada. A entrada não está ordenada, então as reuniões vizinhas na entrada não dizem nada.
Escrever o teste do par com uma condição, como starts[j] < ends[i]. Isso só funciona quando a reunião j começa mais tarde; para reuniões das 5 às 6 e das 0 às 1, nessa ordem, 0 < 6 indica um conflito que não existe.

Perguntas frequentes4

Qual é a complexidade de tempo de Meeting Rooms?

Ordenar as reuniões pelo horário de início custa O(n log n), e a passagem que compara vizinhos é O(n), então o total é O(n log n). Comparar cada par, em vez disso, custa O(n²).

Por que basta comparar cada reunião com a anterior?

Depois de ordenar pelo horário de início, se nenhum conflito tiver sido encontrado até então, as reuniões formam uma cadeia em que cada uma começa no horário de término da anterior ou depois dele. A última reunião da cadeia termina mais tarde. Uma nova reunião que começa no horário de término dela ou depois dele não pode se sobrepor a nenhuma das reuniões anteriores.

Reuniões que se tocam são consideradas sobrepostas?

Não neste problema: uma reunião pode começar exatamente no momento em que outra termina. É por isso que a verificação usa start < previous end. Se reuniões consecutivas fossem proibidas, a verificação seria start ≤ previous end.

Como encontrar o número mínimo de salas de reunião?

Ordene os horários de início e os horários de término em duas listas separadas e, em seguida, percorra ambas: cada início abre uma sala, e cada término que ocorre antes ou no horário do próximo início libera uma. O maior número de salas abertas ao mesmo tempo é a resposta. Responder à pergunta de sim ou não aqui é o mesmo que perguntar se uma sala é suficiente.

Python

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

Casos de teste

Caso 1

Caso 2

Entrada

starts = [9, 13, 10]
ends = [10, 15, 12]

Esperado

true