Escrito por Lúcio Figueiredo
Conhecimento prévio necessário:
Vamos ordenar cada aula de maneira crescente pelo valor .
Defina como o máximo de conhecimento que é possível ganhar usando apenas algumas das aulas . Existem dois casos possíveis ao calcular : Usar a aula ou não usá-la.
Caso 1: Se não usarmos a aula , a transição é simples: .
Caso 2: Se usarmos a aula , a transição já não é tão simples: é necessário tomar cuidado para que a aula não faça interseção com nenhuma outra aula. Como as aulas estão ordenadas por , é possível perceber que uma aula não possuirá interseção com se e somente se . Assim, podemos utilizar uma busca binária para encontrar o maior índice tal que a aula não possui interseção com a aula . Após encontrarmos tal índice , a transição de neste caso se torna .
Assim, considerando os dois casos, concluímos que . A resposta final será .
Complexidade final: (devido à busca binária e a ordenação das aulas). Confira o código abaixo para melhor entendimento.