Mínimo de Remoções para Não Haver Sobreposição
Agendamento guloso mantendo o término mais cedo.
Mínimo de Remoções para Não Haver Sobreposição é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O objetivo das remoções
Você tem intervalos sobrepostos e quer fazer o menor número possível de remoções para que nenhum continue sobreposto. Mantenha o máximo que puder. ✂️
Inverta o problema
Fazer o menor número de remoções equivale a manter o maior número de intervalos não sobrepostos. Resolva a versão de manter e, depois, as remoções serão n menos o número mantido.
Isto é seleção de atividades
Manter o maior número de intervalos não sobrepostos é o clássico problema de seleção de atividades disfarçado. A mesma ideia gananciosa resolve ambos.
Ordene pelo fim
Aqui, a ordem vencedora é pelo horário de fim, não pelo início. Terminar cedo libera a linha do tempo o quanto antes para o próximo intervalo que você possa manter.
intervals.sort(key=lambda x: x[1])A escolha gananciosa
Sempre mantenha o intervalo que termina mais cedo entre os que ainda são compatíveis. Ele deixa o máximo de espaço para os demais.
Acompanhe o último fim mantido
Guarde o fim do último intervalo mantido. O próximo intervalo só será compatível se o seu início estiver nessa fronteira ou depois dela.
if start >= last_end:
last_end = endConte as remoções
Quando um intervalo começa antes de last_end, ele entra em conflito; portanto, você o descarta e adiciona um à contagem de remoções. Caso contrário, você o mantém.
else:
removed += 1Por que o fim mais cedo vence
Um argumento de troca prova isso: substituir qualquer intervalo mantido pelo compatível que termina mais cedo nunca reduz a quantidade que você pode manter.
Trate o limite de contato
Decida se [1, 2] e [2, 3] contam como sobrepostos. Se compartilhar apenas um ponto final for permitido, use start >= last_end como seu teste.
A estratégia gananciosa completa
Faça sort pelo fim, percorra uma vez e conte os conflitos. O custo total é O(n log n) devido à ordenação, mais uma única passagem linear.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Uma estrutura familiar
Esse padrão agenda o maior número de reuniões em uma sala ou acomoda o maior número de tarefas em uma máquina. Identifique-o sempre que os conflitos precisarem ser minimizados.
Verificação rápida
Você mantém gananciosamente os intervalos não sobrepostos.
Recapitulação
O número mínimo de remoções é igual a n menos o máximo que você consegue manter. Ordene pelo fim, mantenha gananciosamente os intervalos compatíveis que terminam mais cedo e conte os restantes. 🚀
Perguntas Frequentes
A aula “Mínimo de Remoções para Não Haver Sobreposição” é grátis?
Sim — o texto completo de “Mínimo de Remoções para Não Haver Sobreposição” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Mínimo de Remoções para Não Haver Sobreposição”?
Agendamento guloso mantendo o término mais cedo. Você pratica Coding Interview Prep 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep 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 4 de 4.
Quanto tempo leva a aula “Mínimo de Remoções para Não Haver Sobreposição”?
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 Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep 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