这是间隔调度的加权变化; 它可以O(N log N)通过动态编程解决。

设一个间隔g(start, stop, score)，然后按排序stop。为了简单起见，让我们现在假设所有stop都是唯一的。

让我们best[i]成为允许使用时可获得的最佳分数g[1], ..., g[i]。当然，我们不必全部使用它们，而且通常也不能，因为我们使用的间隔子集必须不重叠。

• 显然best[0] = 0。也就是说，由于我们不能使用任何间隔，因此我们可以获得的最佳分数是0。
• 对于任何一个1 <= k <= N，我们都有：
  • best[k] = max( best[k-1], best[j] + g[k].score )，在哪里
  • j是最大的索引，使得g[j].stop < g[k].start（j可以为零）

也就是说，考虑到我们被允许使用g[1], ... g[k]，我们可以做的最好的事情就是对这两个选项进行更好的评分：

• 不包括在内g[k]。因此，此选项的分数是best[k-1]。
  • …因为那是我们可以做到的最好 g[1], ... g[k-1]
• 我们包括g[k]，在左边，我们会尽力处理所有不与之重叠的基因g[k]，即all g[1], ..., g[j]，其中g[j].stop < g[k].start和j都尽可能大。因此，此选项的分数是best[j] + g[k].score。

（请注意上式中体现的动态编程的最佳子结构和重叠子问题组件）。

这个问题的总体答案是best[N]，即，当我们允许使用所有基因时，我们可以得到的最高分数。糟糕，我说过基因吗？我的意思是间隔。

这是O(N log N)因为：

• 对所有间隔进行排序 O(N log N)
• 寻找j每一个k被O(log N)使用二进制搜索

如果几个基因可以具有相同的stop值，那么什么都没有改变：您仍然必须搜索最右边的j。在例如Python中，使用会很容易bisect_right。在Java中，标准库二进制搜索不能保证在有关联的情况下返回哪个索引，因此您可以（在许多选项中）进行线性搜索（以获取O(N)最坏情况的性能）或其他一系列二进制搜​​索来查找最正确的索引。

糟糕，我又说了基因？我的意思是间隔。

`