Pular para o conteúdo
</> Entendendo Algoritmos

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