求重叠区间序列中最大和的算法

Question

我正在尝试解决的问题在数字行上有一个区间列表，每个区间都有一个预先定义的分数。我需要返回可能的最大总分。

问题是这些区间是重叠的，在重叠的区间中，我只能使用一个。下面是一个例子。

Intervals   - Score  
   0- 5     -  15  
   4- 9     -  18  
  10-15     -  12  
   8-21     -  19  
  25-30     -  25    

这里，间隔0-5、4-9和8-21重叠。

间隔10-15和8-21也重叠。

最大和将是55 (18+12+25)。

这里需要注意的是，我们选择第一批重叠区间的区间4-9，即使它不具有三个区间中的最高分数。

这是因为选择区间8-21将阻止我们稍后使用区间10-15，从而减少总和(在这种情况下，总和将是19+25=44)。

我正在寻找这个问题的O(nlogn)或O(n)解决方案。我认为可以使用动态编程，但我可能错了。有人能在这里提出一个解决方案/算法吗？

编辑:间隔没有特定的顺序。

Answer 1

这是interval scheduling的加权变体；它可以用dynamic programming在O(N log N)中求解。

设区间为g(start, stop, score)，并按stop排序。为简单起见，我们暂时假设所有stop都是唯一的。

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

• Clearly best[0] = 0.也就是说，因为我们不能使用任何间隔，所以我们能得到的最好分数是0。对于任何索引，我们都有：
  • best[k] = max( best[k-1], best[j] + g[k].score )，其中
    • j是最大的索引，使得1 <= k <= N ( 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]不重叠的基因，即所有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)

• Finding k is O(log N) O(N log N)

• Finding

• j k

如果几个基因可以有相同的stop值，那么没有什么改变:您仍然必须搜索最右边的j。例如，在Python中，使用bisect_right很容易做到这一点。在Java语言中，标准库的二进制搜索不能保证在平局的情况下返回哪个索引，您可以(在许多选项中)以线性搜索(为了O(N)最坏情况下的性能)或另一系列的二进制搜索来查找最正确的索引。

我是不是又说基因了？我的意思是间隔。

相关问题

• Extension of binary search to find the first and last index of the key value

Answer 2

首先，我认为最大值是59，而不是55。如果选择间隔0-5、8-21和25,30，则会得到15+19+25=59。您可以使用某种动态编程来处理此问题。

首先，根据所有间隔的起始点对它们进行排序，然后从一端迭代到另一端。对于列表中的每个项目，选择从该点到最后一个项目的最大和作为max(S[i]+S[j], S[i+1])，其中i是您所在的项目，j是项目之后的第一个非重叠条目(即，第一个项目的开始大于当前项目的结束)。为了加快算法速度，您需要存储每个元素的最大部分和Sj。

为了清楚起见，让我根据这个来解决你的例子。首先，对间隔进行排序：

 1:  0- 5 -  15
 2:  4- 9 -  18
 3:  8-21 -  19
 4: 10-15 -  12
 5: 25-30 -  25

所以,

 S[5] = 25
 S[4] = max(12+S[5], 25)=37
 S[3] = max(19+S[5], S[4])=max(19+25,37)=44
 S[2] = max(18+S[4], S[3])=max(18+37,44)=55
 S[1] = max(15+S[3], S[2])=max(15+44, 55)=59

这是this post中算法的改编，但不幸的是，它的运行时间不是O(n)。如果退化列表中的每一项都与下一项重叠，则会导致它为O(n^2)。

Answer 3

也许可以使用this answer中的方法，至少对于该问题是O(n)。这意味着在区间中迭代一次，并跟踪那些仍然可能导致最佳最终解决方案的区间组合。