Padrão 3: Guloso de sobreposição

"Qual o mínimo de intervalos a remover para o resto não se sobrepor?" Esse tipo de pergunta se resolve com uma escolha gulosa — e a sacada está em ordenar pelo extremo certo: o fim.

🎯

Tente primeiro: Non-overlapping 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, retorne o número mínimo de intervalos a remover para que os restantes não se sobreponham.

Exemplo: [[1,2],[2,3],[3,4],[1,3]] → 1 (remover [1,3] basta).

Carregando editor…

Tentou? A tentação é remover "o que parece atrapalhar mais". A teoria abaixo mostra a regra gulosa simples e por que ela dá o resultado ótimo.

A teoria: manter quem termina cedo

Remover o mínimo para não sobrepor é o mesmo que manter o máximo de intervalos compatíveis (que não se sobrepõem). E aqui está a escolha gulosa, clássica do problema de "agendamento de atividades":

Entre intervalos que competem, mantenha sempre o que termina mais cedo.

Por quê? Porque quem termina mais cedo deixa mais espaço livre à direita para os próximos. Qualquer outra escolha ocuparia a reta por mais tempo sem ganhar nada. Então:

ordene por FIM
fim_mantido = -infinito
remoções = 0
para cada [início, f]:
    se início >= fim_mantido:   # cabe sem sobrepor
        fim_mantido = f         # mantém este
    senão:                      # sobrepõe o último mantido
        remoções += 1           # remove este

Ordenar por fim (e não por início!) é o que faz a regra funcionar: você sempre considera primeiro quem libera a reta mais cedo. Cada intervalo que não cabe depois do último mantido é uma remoção.

Por que o guloso é ótimo aqui? (a intuição)

Imagine que existe uma solução ótima que não escolheu o intervalo de fim mais cedo. Você pode trocar a primeira escolha dela por esse (que termina antes ou junto) sem piorar nada — ele deixa pelo menos tanto espaço quanto o outro. Repetindo o argumento, a escolha gulosa "termina mais cedo" alcança o ótimo. Esse "argumento de troca" é a marca dos algoritmos gulosos corretos.

Complexidade

O sort por fim domina: O(n log n). A varredura é O(n), com O(1) de estado (só o último fim mantido e o contador). Espaço O(1) além da ordenação.

Onde esse guloso aparece

A mesma ideia resolve uma família: número máximo de reuniões/atividades que cabem numa agenda, mínimo de flechas para estourar balões (cada balão é um intervalo; flechas = intervalos restantes após remover sobreposições) e variações de "selecione o máximo de intervalos compatíveis". Sempre que a pergunta for "máximo que cabe sem conflito" ou "mínimo a remover", pense: ordenar por fim + guloso.

🧠 Quiz de fixação

0/4

1. No problema de remover o mínimo de intervalos para não sobreporem, por que ordenar por FIM (e não por início)?

2. Por que 'remover o mínimo para não sobrepor' é equivalente a 'manter o máximo de intervalos compatíveis'?

3. Qual é o 'argumento de troca' que justifica a escolha gulosa?

4. 'Mínimo de flechas para estourar todos os balões (cada balão é um intervalo; uma flecha vertical estoura todos que ela cruza).' Como se relaciona com esta aula?

Resumo

"Mínimo a remover" = "máximo a manter compatível" → guloso.
Ordene por fim e mantenha quem cabe (início >= último fim); o resto é remoção.
Corretude pelo argumento de troca (quem termina cedo deixa mais espaço).
O(n log n) (sort), O(1) de estado; mesma ideia em "máximo de atividades" e "flechas em balões".

Próxima aula: contar a sobreposição máxima — varredura de eventos.

Todas as aulas da seção