Isenção de responsabilidade: o método descrito abaixo não é universal, mas muitas vezes pode resolver um problema ou ajudá-lo a encontrar a solução certa.
Se houver um conjunto de lacunas localizadas em algum eixo (geralmente o eixo do tempo ou índices de algum array) e você precisar escolher alguns deles de maneira ideal para que as lacunas selecionadas não se cruzem, tente usar a programação dinâmica .
Esquema de solução aproximada:
Inicialmente, classificamos as lacunas disponíveis pela borda direita. Vamos iniciar a seguinte dinâmica: dp[i] - a resposta para os primeiros i intervalos.
Vamos recalcular da seguinte forma: primeiro, considere a situação em que esse intervalo não será utilizado, depois é só dp[i] = dp[i-1]. Observe que isso garante que os valores de dp[i] não diminuam à medida que i cresce. E isso é lógico, porque. adicionando uma nova lacuna, não podemos piorar a resposta global: ou simplesmente ignoramos a nova lacuna ou construímos uma variante mais lucrativa usando-a. Agora, se quisermos usar o i-ésimo gap, podemos usar os gaps cujas bordas direitas são menores que a borda esquerda do gap atual, pois devemos escolher um conjunto de gaps não sobrepostos. Para fazer isso, inicialmente classificamos as lacunas pela borda direita, para que agora possamos encontrar com eficiência a posição necessária. Isso pode ser feito analiticamente, se possível, mas no caso geral é possível encontrar uma lacuna com uma pesquisa binária, cuja borda direita é menor que a borda esquerda da atual e, ao mesmo tempo, o máximo possível um. Queremos maximizar a borda certa por motivos gananciosos, porque conforme eu cresço, a resposta só pode aumentar. Assim, encontramos a posição p necessária e recalculamos dp[i] até dp[p] e o i-ésimo intervalo.