Solução Informática Intermediário – Semana 39

por

A ideia desse problema é realizar as tarefas de forma a minimizar o tempo que passa após o tempo limite dele acabar.

Podemos achar uma solução gulosa para esse problema. Vamos ordenar as tarefas pelos seus pontos de inicio de forma crescente, e caso haja empate, pelo termino de forma crescente. A partir daí podemos simular pelo tempo e obter a resposta.

A razão por quê isso funciona é pelo fato de se tivermos duas tarefas a e b que teminam uma após a outra, caso colquemos na ordem contraria, teríamos uma solução pior.

Código para melhor entendimento:

https://gist.github.com/fredbr/11aede4a1a57b87d9c221dda6f8a2b5f