Descargo de responsabilidad: el método que se describe a continuación no es universal, pero a menudo puede resolver un problema o ayudarlo a encontrar la solución correcta.
Si hay un conjunto de brechas ubicadas en algún eje (generalmente el eje del tiempo o índices de alguna matriz) y necesita elegir algunas de ellas de manera óptima para que las brechas seleccionadas no se crucen, entonces debe intentar usar programación dinámica .
Esquema de solución aproximado:
Inicialmente, ordenamos los espacios disponibles por el borde derecho. Comencemos con la siguiente dinámica: dp[i] - la respuesta para los primeros intervalos i.
Recalcularemos de la siguiente manera: primero, considere la situación de que este intervalo no se usará, luego solo dp[i] = dp[i-1]. Tenga en cuenta que esto asegura que los valores de dp[i] no disminuyan a medida que i crece. Y esto es lógico, porque. agregando una nueva brecha, no podemos empeorar la respuesta global: o simplemente ignoramos la nueva brecha, o construimos una variante más rentable usándola. Ahora, si queremos usar el espacio i-ésimo, entonces podemos usar esos espacios cuyos bordes derechos son menores que el borde izquierdo del espacio actual, ya que debemos elegir un conjunto de espacios que no se superpongan. Para hacer esto, inicialmente clasificamos los espacios por el borde derecho, de modo que ahora podamos encontrar de manera eficiente la posición requerida. Esto se puede hacer analíticamente, si es posible, pero en el caso general es posible encontrar una brecha con un binsearch, cuyo borde derecho es menor que el borde izquierdo del actual y, al mismo tiempo, el máximo posible. uno. Queremos maximizar el borde derecho por razones codiciosas, porque a medida que crece, la respuesta solo puede aumentar. En consecuencia, encontramos la posición p requerida y recalculamos dp[i] a través de dp[p] y el i-ésimo intervalo.