免责声明：下面描述的方法并不通用，但它通常可以解决问题或帮助您找到正确的解决方案。
如果在某个轴上有一组间隙（通常是时间轴或某个数组的索引）并且您需要以最佳方式选择其中的一些间隙以使所选间隙不相交，那么您应该尝试使用动态规划.
大概的解决方案：
最初，我们按右边界对可用间隙进行排序。让我们开始以下动态：dp[i] - 前 i 个区间的答案。
我们将重新计算如下：首先考虑不使用这个区间的情况，那么只要dp[i] = dp[i-1]。注意，这样可以保证dp[i]的值不会随着i的增长而减少。这是合乎逻辑的，因为。添加一个新的差距，我们不能恶化全局答案：要么我们简单地忽略新的差距，要么我们使用它构建一个更有利可图的变体。现在，如果我们想使用第 i 个间隙，那么我们可以使用右边界小于当前间隙左边界的那些间隙，因为我们必须选择一组不重叠的间隙。为此，我们最初按右边界对间隙进行排序，以便现在我们可以有效地找到所需的位置。如果可能的话，这可以通过分析来完成，但在一般情况下，可以通过 binsearch 找到一个间隙，其右边界小于当前边界的左边界，同时，最大可能一。出于贪婪的原因，我们想最大化右边界，因为随着我的成长，答案只会越来越多。因此，我们找到所需的位置 p 并通过 dp[p] 和第 i 个间隔重新计算 dp[i]。