O básico de intervalos e ordenação
Passo 1 de 8
Quatro reuniões, desenhadas na ordem em que foram marcadas. Cada uma é só um início e um fim.
A ideia
Um intervalo é só um par: início e fim. Dois deles se sobrepõem quando cada um começa antes de o outro terminar — um teste, sem casos especiais.
Conferir todos os pares custa n ao quadrado. Ordenar pelo início custa n log n e depois garante algo útil: todo intervalo que você encontrar em seguida começa no mesmo ponto ou depois daquele que você está segurando.
Exemplo do mundo real
Uma agenda compartilhada desenhada da esquerda para a direita ao longo do dia. Ninguém compara a quarta reunião de terça com a primeira — os conflitos ficam visíveis porque as barras estão dispostas em ordem de tempo, que é exatamente o que ordenar pelo início faz.
O código
Sua vez
O que isto imprime?
spans = [(5, 8), (1, 4), (1, 2)]
spans.sort()
print(spans[0])Mini quiz
1 / 3