Padrão 1: Ordenar e fundir (merge)
Fundir intervalos que se sobrepõem é o "olá, mundo" da seção. E mostra, na forma mais pura, o método que vale para quase tudo aqui: ordene por início, depois varra uma vez.
Tente primeiro: Merge Intervals
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 [início, fim], funda todos os que se sobrepõem e retorne a lista resultante (ordenada por início).
Exemplo: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] (o [1,3] e o [2,6] se sobrepõem → [1,6]).
Tentou? Sem ordenar, você fica comparando cada intervalo com todos os outros (O(n²)) e ainda se perde com sobreposições em cadeia. A teoria abaixo mostra por que ordenar primeiro torna tudo simples.
A teoria: ordenar transforma o problema
Por que ordenar por início ajuda tanto? Porque, depois disso, qualquer intervalo que se sobreponha a um anterior só pode se sobrepor ao último que você processou (todos os anteriores já terminaram mais à esquerda). Isso reduz "comparar com todos" a "comparar com o último do resultado":
ordena por início
resultado = []
para cada [início, fim]:
se resultado não vazio E início <= fim do último do resultado:
# sobrepõe → estende o fim do último
último.fim = max(último.fim, fim)
senão:
# não sobrepõe → começa um bloco novo
resultado.append([início, fim])
Repare no max ao estender: o intervalo atual pode estar contido no
último (ex.: [1,6] engolindo [2,4]), então o fim não pode encolher. Veja a
varredura — a faixa de cima é a entrada (atual em destaque), a de baixo é o
resultado sendo construído e estendido:
Por que é O(n log n) tempo e O(n) espaço?
O sort custa O(n log n) e domina. A varredura é uma única passada O(n), comparando cada intervalo só com o último do resultado. O espaço é O(n) para a lista de saída (ou O(log n)–O(n) do próprio sort). A força bruta de comparar todos os pares seria O(n²) — ordenar é o que derruba isso.
O reflexo que vale a seção
Esse é o template-mãe dos intervalos: ordenar por um extremo + uma varredura comparando com o estado acumulado. Guarde a forma do código — as próximas aulas são variações dela (inserir muda o "quando começar a fundir", o guloso muda o critério de ordenação, a varredura de eventos muda o que acumula).
🧠 Quiz de fixação
0/41. Por que ordenar por início simplifica o merge de intervalos?
2. Ao fundir um intervalo que se sobrepõe, por que usar max(fim_último, fim_atual) em vez de só fim_atual?
3. Qual a complexidade do merge e o que a domina?
4. Qual é o 'template-mãe' dos problemas de intervalo, do qual o merge é o exemplo?
Resumo
- Merge: ordene por início; varra fundindo quando
início <= fim do último(commaxno fim). - O(n log n) (sort domina), O(n) de espaço; bem melhor que o O(n²) ingênuo.
- É o template-mãe da seção: ordenar + varrer com estado acumulado.
Próxima aula: inserir um intervalo num conjunto já ordenado.