Pular para o conteúdo

O básico de intervalos e ordenação

Aula 1 de 4 · 4 min

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

Dois intervalos a e b se sobrepõem quando: