Pular para o conteúdo

Agendamento de intervalos

Aula 2 de 5 · 5 min

Agendamento de intervalos

Passo 1 de 10

Cinco reservas para uma sala. Aceite o máximo possível sem que duas se sobreponham.

A ideia

Você quer o maior número possível de tarefas sem sobreposição em uma única sala. Ordene pelo horário de término e percorra a lista pegando toda tarefa que começa no fim da última escolhida ou depois dele.

Só terminar cedo importa, porque a tarefa que acaba primeiro deixa a maior parte do dia para todo o resto. Duração e horário de início são pistas falsas.

Exemplo do mundo real

Uma única ilha de edição em uma produtora de pós-produção. Seis clientes querem usá-la hoje; quem cuida da agenda aceita a reserva que libera a ilha mais cedo, e assim o maior número de clientes é atendido — não quem pediu primeiro, nem a tarefa mais longa.

O código

Sua vez

Coloque os passos em ordem.

  1. Se ela começar nesse horário ou depois, aceite a tarefa e passe o horário em que a sala fica livre para o fim dela
  2. Ordene todas as tarefas pelo horário de término
  3. Senão, pule a tarefa, porque ela se sobrepõe ao que já está reservado
  4. Comece com a sala livre desde menos infinito
  5. Compare o início da próxima tarefa com o horário em que a sala fica livre

Mini quiz

1 / 3

Qual critério torna correto o guloso do agendamento de intervalos (interval scheduling)?