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