Mescle Intervalos Sobrepostos
Combine intervalos que se tocam ou se sobrepõem.
Mescle Intervalos Sobrepostos é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O objetivo da mesclagem
Dada uma série de intervalos, você quer mesclar aqueles que se tocam ou se sobrepõem no menor número possível de intervalos não sobrepostos. 🧩
Quando dois intervalos se sobrepõem
Dois intervalos se sobrepõem quando um começa antes que o outro termine. Depois de ordenar pelo início, isso significa que o próximo início é menor ou igual ao fim atual.
Ordene primeiro, sempre
A mesclagem só funciona da esquerda para a direita se os intervalos estiverem ordenados, então comece ordenando-os pelo início. Essa é a base de toda a varredura.
intervals.sort(key=lambda x: x[0])Mantenha um intervalo atual
Percorra a lista ordenada mantendo um único intervalo mesclado atual. Cada novo intervalo o estende ou inicia um novo intervalo.
Estenda quando houver sobreposição
Se o próximo início estiver dentro do intervalo atual, eles se sobrepõem; portanto, você deve estender o fim atual até o maior dos dois fins.
cur_end = max(cur_end, end)Escolha o maior fim
Sempre use o máximo para o novo fim. Um intervalo curto contido em um intervalo longo não deve diminuir o intervalo que você já construiu.
Feche e abra um novo intervalo
Se o próximo início estiver depois do fim atual, haverá uma lacuna. Adicione o intervalo concluído à sua resposta e comece um novo intervalo atual.
result.append([cur_start, cur_end])Não se esqueça do último
O laço constrói o intervalo final, mas nunca o adiciona. Depois que o laço terminar, use append nesse último intervalo atual para que ele não seja perdido.
Tocar também conta como sobreposição
Decida se [1, 3] e [3, 5] devem ser mesclados. Normalmente, sim, portanto use start <= cur_end. Leia o problema para confirmar essa regra de limite.
A varredura completa
Uma passagem após a ordenação fornece todos os intervalos mesclados, portanto o método completo executa em O(n log n): a ordenação mais uma varredura linear.
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eUm uso comum
A mesclagem é útil em calendários e sistemas de reservas: compacte os blocos ocupados para visualizar o tempo realmente livre. Muitos problemas de competições escondem exatamente essa mesma estrutura.
Verificação rápida
Você mescla os intervalos depois de ordená-los pelo início.
Recapitulação
Ordene pelo início, mantenha um intervalo atual e estenda-o usando o máximo quando houver sobreposição, ou insira o intervalo e recomece quando houver uma lacuna. Lembre-se do append final. 🚀
Perguntas Frequentes
A aula “Mescle Intervalos Sobrepostos” é grátis?
Sim — o texto completo de “Mescle Intervalos Sobrepostos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Mescle Intervalos Sobrepostos”?
Combine intervalos que se tocam ou se sobrepõem. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Mescle Intervalos Sobrepostos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Ordene Intervalos pelo Início
- Mescle Intervalos Sobrepostos
- Varredura de Linha para a Sobreposição Máxima
- Mínimo de Remoções para Não Haver Sobreposição