Solução Informática – Nivel Intermediário – Semana 23

Escrito por Lúcio Figueiredo

Conhecimento prévio necessário:

• Programação Dinâmica
• Busca Binária

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.