Comparecer a todas as reuniões
A missão
Problema
Uma agenda lista reuniões como pares [start, end], sem nenhuma ordem em particular. Decida se uma pessoa consegue participar de todas as reuniões do início ao fim. Uma reunião que termina exatamente quando outra começa não é problema, porque a pessoa pode ir direto de uma para a seguinte.
Exemplos
Input: meetings = [[0, 30], [5, 10], [15, 20]]
Output: False
Por quê: a reunião longa engole as outras duas
Input: meetings = [[7, 10], [2, 4], [4, 7]]
Output: True
Por quê: em ordem cronológica, as reuniões só se tocam nas extremidades
Input: meetings = []
Output: True
Por quê: edge case: uma agenda vazia não tem nada que possa entrar em conflito
Dicas
0 / 3
Comparar cada par de reuniões funciona, mas é quadrático. Pense em quais pares podem de fato entrar em conflito quando você os olha em uma ordem sensata.
Depois de ordenar pelo horário de início, uma reunião só pode colidir com algo que começa antes dela, e a que tem mais chance de ainda estar acontecendo é a imediatamente anterior.
Ordene pelo horário de início e percorra a lista uma vez. Se alguma reunião começar antes de a reunião anterior terminar, retorne False. Se o percurso chegar ao fim, retorne True.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Solução
Com as reuniões ordenadas pelo horário de início, a única forma de duas delas se sobreporem é alguma reunião começar antes de a sua antecessora imediata terminar: se vizinhas nessa ordem nunca se sobrepõem, os seus horários de término também ficam em ordem, então nada mais atrás consegue avançar além delas. Isso transforma uma pergunta sobre todos os pares em uma comparação por par adjacente, com um menor-que estrito para que reuniões que só se tocam passem. O tempo é O(n log n) por causa da ordenação, e o espaço é O(n) para a cópia ordenada.
def can_attend_all(meetings):
ordered = sorted(meetings) # by start time
for prev, cur in zip(ordered, ordered[1:]):
if cur[0] < prev[1]: # starts before the last one ends
return False
return True
print(can_attend_all([[0, 30], [5, 10], [15, 20]])) # -> False
print(can_attend_all([[7, 10], [2, 4], [4, 7]])) # -> True
print(can_attend_all([])) # -> TrueTravou na ideia, e não no código? Meeting Rooms explica isso.