Padrão 2: Inserir num conjunto ordenado
E quando a lista já está ordenada e sem sobreposições, e você precisa encaixar um novo intervalo? Aproveitar que ela já está organizada permite resolver em uma passada, sem reordenar — dividindo a lista em três fases.
Tente primeiro: Insert Interval
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dada uma lista de intervalos ordenada e sem sobreposições e um novo intervalo, insira-o (fundindo se necessário) mantendo a lista ordenada e sem sobreposições.
Exemplo: intervalos = [[1,3],[6,9]], novo = [2,5] → [[1,5],[6,9]].
Tentou? Dá para adicionar o novo, reordenar e fundir tudo (a aula anterior) — mas isso joga fora a informação de que a lista já estava ordenada. A teoria abaixo faz em O(n), sem sort.
A teoria: três fases na reta
Como a lista já está ordenada e sem sobreposições, os intervalos se dividem naturalmente em três grupos em relação ao novo intervalo:
1. ANTES: terminam antes de o novo começar (fim < novo.início)
→ copie-os intactos
2. SOBREPÕEM: tocam o novo (início <= novo.fim)
→ funda todos no novo (min dos inícios, max dos fins)
3. DEPOIS: começam depois de o novo terminar
→ copie-os intactos
Você percorre a lista uma vez, passando por essas três fases em ordem. A fase
2 é o coração: enquanto o intervalo atual toca o novo, ele é absorvido —
novo = [min(inícios), max(fins)]. No fim da fase 2, o novo (já fundido) entra
no resultado, e a fase 3 só copia o resto.
Veja as três fases — repare o novo (escalar) crescendo ao absorver os
intervalos da fase 2:
Por que é O(n) tempo (sem sort!)?
A lista já vem ordenada, então não pagamos o O(n log n) do merge: uma única passada linear classifica cada intervalo numa das três fases → O(n) de tempo, O(n) de espaço para a saída. É a vantagem de explorar a estrutura dada (ordenada) em vez de reordenar do zero.
A lição
Quando o enunciado garante que a entrada já tem uma ordem, não a desperdice. Aqui, "já ordenada" transforma um problema de merge (O(n log n)) num de três fases lineares (O(n)). Sempre pergunte: o que a entrada já me dá de graça?
🧠 Quiz de fixação
0/41. Por que dá para inserir em O(n) (sem ordenar), enquanto o merge geral é O(n log n)?
2. Quais são as três fases da inserção?
3. Na fase de sobreposição, como o novo intervalo é atualizado?
4. Qual a lição transferível desta aula?
Resumo
- Inserir numa lista ordenada e sem sobreposições: três fases — antes, funde, depois — numa passada.
- O(n) de tempo (sem sort!), porque a entrada já vem ordenada.
- Lição: explore a estrutura dada em vez de reorganizar do zero.
Próxima aula: escolher o que manter com raciocínio guloso.