Avis de non-responsabilité : la méthode décrite ci-dessous n'est pas universelle, mais elle peut souvent résoudre un problème ou vous aider à trouver la bonne solution.
S'il y a un ensemble d'écarts situés sur un axe (généralement l'axe du temps ou les indices d'un tableau) et que vous devez en choisir certains de manière optimale afin que les écarts sélectionnés ne se croisent pas, alors vous devriez essayer d'utiliser la programmation dynamique .
Schéma de solution approximatif :
Initialement, nous trions les espaces disponibles par la bordure droite. Commençons la dynamique suivante : dp[i] - la réponse pour les premiers intervalles i.
Nous allons recalculer comme suit : d'abord, considérons la situation où cet intervalle ne sera pas utilisé, puis simplement dp[i] = dp[i-1]. Notez que cela garantit que les valeurs de dp[i] ne diminuent pas à mesure que i grandit. Et c'est logique, parce que. en ajoutant un nouvel écart, on ne peut pas aggraver la réponse globale : soit on ignore simplement le nouvel écart, soit on construit une variante plus rentable en l'utilisant. Maintenant, si nous voulons utiliser le i-ième espace, nous pouvons utiliser les espaces dont les bords droits sont inférieurs au bord gauche de l'espace actuel, car nous devons choisir un ensemble d'espaces qui ne se chevauchent pas. Pour ce faire, nous avons d'abord trié les espaces par la bordure droite, de sorte que nous puissions maintenant trouver efficacement la position requise. Cela peut être fait analytiquement, si possible, mais dans le cas général, il est possible de trouver un écart avec un binsearch dont le bord droit est inférieur au bord gauche de celui en cours et, en même temps, le maximum possible un. Nous voulons maximiser la bonne frontière pour des raisons gourmandes, parce que à mesure que je grandis, la réponse ne peut qu'augmenter. En conséquence, nous trouvons la position requise p et recalculons dp[i] à dp[p] et le i-ième intervalle.