Calendário de aulas
O problema que apresenta o algoritmo guloso: escolha a aula que termina primeiro, depois a próxima que começa depois dela, e repita. Aqui a estratégia gulosa chega à resposta ótima, mas só porque este problema tem essa propriedade.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
function calendarioGuloso(aulas) {
// a aula que termina primeiro vem antes
const ordenadas = [...aulas].sort((a, b) => a.fim - b.fim);
const escolhidas = [];
let ultimoFim = -Infinity;
for (const aula of ordenadas) {
if (aula.inicio >= ultimoFim) { // não conflita com a última escolhida
escolhidas.push(aula.nome);
ultimoFim = aula.fim;
}
}
return escolhidas;
}Você quer assistir ao maior número possível de aulas em uma sala, sem sobreposição de horários.
Sendo examinadaEscolhidaRecusada ou ainda não examinada
9h
10h
11h
12h
Arte 9:00–10:00
Inglês 9:30–10:30
Matemática 10:00–11:00
Computação 10:30–11:30
Música 11:00–12:00