Seleção de Atividades pelo Término Mais Cedo
Agende o maior número de eventos sem sobreposição.
Seleção de Atividades pelo Término Mais Cedo é 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 problema do agendamento
Dado um conjunto de eventos com horários de início e fim, a seleção de atividades pede o maior número de eventos que você pode acompanhar sem que dois se sobreponham. 📅
Sobreposição significa conflito
Duas atividades entram em conflito se uma começa antes de a outra terminar. Você só pode escolher um evento de qualquer par sobreposto.
A regra vencedora
A chave gulosa é sempre escolher o evento que termina mais cedo entre os ainda disponíveis. Terminar cedo deixa o maior espaço possível para os outros.
Ordenar pelo horário de término
Comece ordenando todas as atividades pelo horário de término. Agora, a melhor próxima escolha é simplesmente a próxima nesta ordem que couber.
events.sort(key=lambda e: e[1])Acompanhar o último término
Mantenha uma variável para o horário de término da última escolha. Qualquer novo evento deve começar neste horário ou depois dele para ser compatível.
last_end = -1Percorrer e selecionar
Percorra a lista ordenada uma vez. Se um evento começar no horário do último término ou depois dele, escolha-o e atualize o último término para seu horário de término.
for s, f in events:
if s >= last_end:
count += 1
last_end = fExecuta em n log n
O custo está na sort, O(n log n), seguida de uma única passagem linear. Isso é rápido o suficiente até para entradas de competição muito grandes.
Por que o término mais cedo vence
Terminar primeiro libera a linha do tempo mais cedo, portanto nunca pode bloquear um plano melhor. Trocá-lo por qualquer programação ótima mantém a mesma qualidade.
O início mais cedo falha
Escolher pelo início mais cedo pode selecionar um evento longo que ocupa o dia inteiro. A duração, por si só, também engana; por isso, confie no horário de término.
Lidar com toques nas fronteiras
Decida se um evento que termina exatamente quando outro começa conta como conflito. Use s >= fim_anterior para permitir eventos consecutivos.
Um formato comum em competições
Esse padrão aparece por trás de muitas tarefas: reservar salas, assistir a programas ou executar tarefas. Identifique-o e a regra do término mais cedo se aplicará.
Verificação rápida
Você quer o número máximo de atividades que não se sobrepõem.
Recapitulação
Ordene as atividades pelo horário de término e escolha cada uma que comece depois do término da sua última escolha. Uma ordenação mais uma passagem fornecem o maior conjunto possível. 🚀
Perguntas Frequentes
A aula “Seleção de Atividades pelo Término Mais Cedo” é grátis?
Sim — o texto completo de “Seleção de Atividades pelo Término Mais Cedo” é 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 “Seleção de Atividades pelo Término Mais Cedo”?
Agende o maior número de eventos sem sobreposição. 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 “Seleção de Atividades pelo Término Mais Cedo”?
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
- A Mentalidade Gulosa
- Seleção de Atividades pelo Término Mais Cedo
- Mochila Fracionária por Proporção
- Identifique Quando a Estratégia Gulosa Falha