Varredura de Linha para a Sobreposição Máxima
Conte intervalos simultâneos usando eventos.
Varredura de Linha para a Sobreposição Máxima é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 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.
A questão da sobreposição máxima
Quantos intervalos cobrem o mesmo momento ao mesmo tempo? A contagem máxima é a sobreposição máxima, o ponto mais movimentado da sua linha do tempo. 📈
Pense em eventos
Pare de pensar em intervalos inteiros. Divida cada um em dois eventos: um +1 quando começa e um -1 quando termina.
Crie a lista de eventos
Para cada intervalo, adicione um evento de início e um evento de fim à mesma lista. Cada evento contém uma posição e um delta de mais ou menos um.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Ordene os eventos
sort cada evento pela posição para percorrer a linha do tempo da esquerda para a direita, processando as mudanças na ordem correta.
events.sort()Percorra e conte
Percorra os eventos ordenados mantendo um contador acumulado. Adicione cada delta ao passar por ele; o contador representa quantos intervalos estão ativos agora.
active = 0
for pos, delta in events:
active += deltaAcompanhe o pico
Depois de cada atualização, compare o contador com o melhor valor obtido até então. O maior valor que o contador alcançar será a sobreposição máxima.
best = max(best, active)O truque do desempate
Quando as posições são iguais, a ordem importa. Se um fim em x deve liberar o espaço antes de um início em x, ordene os fins antes dos inícios no mesmo ponto.
Codifique os deltas para ordenar corretamente
Uma maneira elegante de desempatar é escolher os deltas de modo que a ordenação da tupla faça isso por você. Coloque o delta -1 antes do +1 quando as posições coincidirem.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tiePor que é rápido
Você cria 2n eventos, faz sort uma vez e percorre a lista uma vez. O método completo é O(n log n), dominado por essa única ordenação.
Onde você encontra isso
A sobreposição máxima resolve problemas clássicos, como determinar o número mínimo de salas necessárias para reuniões ou o pico de usuários simultâneos em um servidor.
Além de apenas contar
A mesma varredura pode ser facilmente ampliada: acompanhe o comprimento total coberto ou encontre todas as posições onde a contagem muda, tudo em uma única passagem linear.
Verificação rápida
Você percorre os eventos para encontrar a sobreposição máxima.
Recapitulação
Transforme os intervalos em eventos de início +1 e fim -1, ordene-os e percorra um contador para encontrar o pico. Desempate colocando os fins antes dos inícios. 🚀
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “Varredura de Linha para a Sobreposição Máxima” é grátis?
Sim — o texto completo de “Varredura de Linha para a Sobreposição Máxima” é 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 “Varredura de Linha para a Sobreposição Máxima”?
Conte intervalos simultâneos usando eventos. 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 3 de 4.
Quanto tempo leva a aula “Varredura de Linha para a Sobreposição Máxima”?
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