Síntese: qual padrão usar?
Quatro padrões de intervalos cobertos. Como a seção é enxuta, a árvore de decisão também é — mas o reflexo de ordenar pelo extremo certo é o que separa quem resolve de quem trava.
A árvore de decisão da seção
1. Preciso FUNDIR intervalos sobrepostos numa lista qualquer?
→ ordene por INÍCIO + varra fundindo no último do resultado
2. A lista JÁ está ordenada e vou INSERIR um intervalo?
→ três fases (antes / funde / depois), em O(n) sem sort
3. "Mínimo a remover" / "máximo que cabe sem conflito"?
→ GULOSO: ordene por FIM, mantenha quem termina mais cedo
4. "Quantos recursos/salas ao mesmo tempo?" / "sobreposição máxima"?
→ VARREDURA DE EVENTOS (+1 no início, −1 no fim) ou min-heap dos fins
A pergunta que orienta tudo: ordenar por início ou por fim? Início para fundir/inserir (processar na ordem da reta); fim para escolhas gulosas (quem libera espaço mais cedo).
O mapa completo da seção
| Padrão | Pergunta-chave | Ordena por | Tempo |
|---|---|---|---|
| Merge | "funda os sobrepostos" | início | O(n log n) |
| Insert | "insere em lista ordenada" | (já ordenada) | O(n) |
| Guloso | "mínimo a remover / máximo que cabe" | fim | O(n log n) |
| Varredura de eventos | "quantos ao mesmo tempo / salas" | início e fim | O(n log n) |
Repare: quase tudo é O(n log n) dominado pelo sort — exceto inserir, que aproveita a lista já ordenada e cai para O(n). A varredura em si é sempre linear; a criatividade está em por qual extremo ordenar e o que acumular (último intervalo? contador de ativos?).
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 6+ acertos: pronto para a prova.
🧠 Quiz da seção: Intervalos
0/61. 'Dada uma agenda, qual o número MÁXIMO de reuniões que cabem sem se sobrepor?' Qual padrão?
2. 'Funda intervalos sobrepostos' e 'insere num conjunto já ordenado': por que as complexidades diferem?
3. 'Qual o ponto do tempo com mais intervalos sobrepostos?' Qual técnica?
4. 'Mínimo de flechas para estourar balões (intervalos no eixo x)' usa qual padrão?
5. 'Some duas listas de intervalos JÁ ordenadas, devolvendo as interseções.' Qual abordagem?
6. Qual é a decisão que orienta quase todos os problemas de intervalo?
Pronto para a prova?
A prova final da seção Intervalos tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil (Car Pooling) aplica a varredura de eventos num cenário novo (passageiros que entram e saem): exatamente o raciocínio das salas de reunião. As quatro aulas cobrem tudo que você precisa.
Boa prova! Volte para a página da seção e clique em "Prova final".