Por simplicidad sumemos los pesos de todos los intervalos y a ello restemos los valores los intervalos que quedarán al final.

Subtarea 1:

En esta subtarea como los intervalos son puntos y todos tienen costo 1, simplemente podemos quedarnos con la mayor cantidad de puntos.

Subtarea 2:

En esta subtarea como los intervalos son puntos, para cada posición nos quedamos con el intervalo con mayor peso en cada posición

Subtarea 3:

Como ~k = 1~, y ~w_i = 1~, es simplemente decir la mayor cantidad de intervalos que se pueden tomar tal que no se intersecten, se puede hacer con dp o con greedy ordenando por ~e_i~ y cogiendo el primer intervalo posible repetivamente.

Subtarea 4:

Como ~k = 1~ es simplemente decir la mayor suma de pesos de intervalos que se pueden tomar tal que no se intersecten, se puede hacer con dp.

Subtarea 5:

Esta subtarea puede ser resuelta por implementaciones más sencillas de la solución general.

Subtarea 6:

Por conveniencia, llamaremos bueno a un conjunto de intervalos si todos los componentes conectados tienen un tamaño ~K~ como máximo. Toma la unión de intervalos en cada componente conexa. Los intervalos representados por cada componente son disjuntos. A partir de esto, usaremos el enfoque DP donde fijamos la unión de intervalos y llenamos cada componente.

Discretice los intervalos para que tengan coordenadas de hasta ~2\cdot{N}~ y defina ~f (x)~ como el costo máximo de los intervalos tal que los intervalos elegidos sean buenos, considerando solo los intervalos cuyo punto final más a la derecha es menor o igual a ~x~. La respuesta es por lo tanto $$\displaystyle\sum_{i=1}^n{w_i} - f(2\cdot{N})$$.

Si definimos ~g(a, b)~ como el costo máximo de los intervalos a tomar tal que, considerando solo los intervalos que se encuentran completamente en ~[a, b]~, el conjunto resultante de intervalos pertenece a un solo componente conexo bueno, entonces tenemos que ~f (x) = \max_{0\le a<x}(f (a) + g(a + 1, x))~. Para calcular ~g(a, b)~, simplemente podemos encontrar los intervalos que se encuentran completamente dentro del intervalo ~[a, b]~ y tomar los ~k~ de mayor peso.

Esto puede resultar en no tener el único componente conectado, pero no importa ya que cada componente conectado seguirá siendo bueno de todas formas. Dado que ~g(a, b)~ se puede calcular ingenuamente en tiempo ~O(N^3 \log{N} )~, queda por calcular ~g~ de manera eficiente. Si barrimos ~a~ de ~0~ a ~x - 1~, con un poco de contabilidad cuidadosa podemos calcular ~f (x)~ en tiempo ~O(x)~, lo cual nos daría un algoritmo en ~O(N^2)~.

Consideraremos todos los intervalos con punto final izquierdo menor o igual que el ~x~ activo, y además dividirlos en intervalos que se extienden más allá de ~x~ e intervalos que no lo hacen. Cuando barremos a en orden creciente, algunos intervalos se vuelven inactivos. Deseamos mantener la suma de los ~K~ intervalos más pesados ​​que no pasan de ~x~, lo que se puede hacer barriéndolos en orden decreciente de peso y asegurándonos de no haber incluido más de ~K~ de ellos.