Дисклеймер: способ, описанный ниже, не является универсальным, однако зачастую может решить задачу или помочь прийти к правильному решению.
Если имеется набор промежутков, расположенных на некоторой оси (обычно ось времени или индексы какого-нибудь массива) и необходимо выбрать некоторые из них оптимальным образом, чтобы выбранные промежутки не пересекались, то стоит попробовать применить динамическое программирование.
Примерная схема решения:
Изначально отсортируем имеющиеся промежутки по правой границе. Заведем следующую динамику: dp[i] - ответ для первых i промежутков.
Пересчитывать будем следующим образом: во-первых, рассмотрим ситуацию, что данный промежуток не будет использоваться, тогда просто dp[i] = dp[i-1]. Заметим, что это обеспечивает неубывание значений dp[i] с ростом i. И это логично, т.к. добавляя новый промежуток, мы не можем ухудшить глобальный ответ: либо мы просто проигнорируем новый промежуток, либо сконструируем более выгодный вариант с помощью него. Теперь, если мы хотим использовать i-й промежуток, то мы можем использовать те промежутки, правые границы которых меньше левой границы текущего промежутка, так как мы должны выбрать набор непересекающихся промежутков. Для этого мы изначально сортировали промежутки по правой границе, чтобы сейчас можно было эффективно найти необходимую позицию. Это можно делать аналитически, если это возможно, но в общем случае можно найти бинпоиском промежуток, правая граница которого меньше левой границы текущего и при этом максимально возможная. Максимизировать правую границу мы хотим из жадных соображений, т.к. с ростом i ответ может только увеличиваться. Соответственно, находим необходимую позицию p и пересчитываем dp[i] через dp[p] и i-й промежуток.