Ordene Intervalos pelo Início
Ordene os eventos antes de processá-los.
Ordene Intervalos pelo Início é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 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 que é um intervalo
Um intervalo é apenas um par de números, um início e um fim, como [2, 5]. A maioria dos problemas de intervalos consiste em uma lista desses pares. 📏
A ordem traz clareza
Os intervalos brutos chegam em qualquer ordem, o que dificulta raciocinar sobre eles. Ordená-los primeiro transforma o caos em uma varredura organizada da esquerda para a direita.
Ordene pelo início
O procedimento padrão é ordenar pelo valor de início. Agora cada intervalo começa no mesmo ponto ou depois do anterior, então você pode percorrê-los uma única vez.
intervals.sort(key=lambda x: x[0])Tuplas são ordenadas naturalmente
Se você armazenar os intervalos como tuplas, o Python os ordenará pelo primeiro elemento e depois pelo segundo, automaticamente. Nem é necessário usar uma função de chave aqui.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Por que começar pelo início
Ordenar pelo início permite processar os eventos em ordem de tempo. O próximo intervalo só pode começar depois, e essa é a principal invariante da varredura.
Empates no início
Quando dois intervalos têm o mesmo início, a chave secundária decide a ordem. Ordenar por (início, fim) mantém os menores primeiro, o que costuma ajudar.
intervals.sort(key=lambda x: (x[0], x[1]))Às vezes, ordene pelo fim
Alguns problemas, como programar o maior número de eventos, ordenam pelo fim. Escolha a chave que corresponda ao que sua varredura precisa saber.
intervals.sort(key=lambda x: x[1])O custo da ordenação
Ordenar leva tempo O(n log n), o que é barato e geralmente domina esses problemas. A varredura seguinte custa apenas O(n).
Mantenha os dados extras associados
Se cada intervalo tiver um identificador ou peso, ordene o registro inteiro, não apenas os limites. A chave controla a ordem enquanto os dados permanecem associados.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Ordene e depois percorra
Quase todo algoritmo de intervalos segue o padrão sort primeiro, depois percorra. Acerte a ordem e mesclar, contar e programar se tornam laços simples.
Um modelo mental rápido
Imagine os intervalos como convidados chegando a uma festa. Ordená-los pelo início os organiza pelo horário de chegada, para que você possa recebê-los um por um.
Verificação rápida
Você está prestes a mesclar uma lista de intervalos.
Recapitulação
Um intervalo é um par de início e fim, e ordenar pelo início transforma uma lista desorganizada em uma varredura clara. Ordene primeiro e depois processe para a frente em O(n). 🚀
Perguntas Frequentes
A aula “Ordene Intervalos pelo Início” é grátis?
Sim — o texto completo de “Ordene Intervalos pelo Início” é 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 “Ordene Intervalos pelo Início”?
Ordene os eventos antes de processá-los. 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 1 de 4.
Quanto tempo leva a aula “Ordene Intervalos pelo Início”?
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