用于在重叠间隔序列中找到最大和的算法

我试图解决的问题是在数字行上有一个间隔列表,每个间隔都有一个预定义的分数.我需要返回最大可能的总分.

问题是间隔重叠,重叠间隔我只能使用一个.这是一个例子.

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)解决方案.我认为可以使用动态编程,但我可能错了.有人可以建议一个可以解决这个问题的解决方案/算法吗？

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

这是区间调度的加权变化; 它可以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],即所有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)最坏情况的性能)或其他一系列二进制搜​​索来查找最正确的指数.

哎呀我再说基因了吗？我的意思是间隔.

相关问题

扩展二进制搜索以查找键值的第一个和最后一个索引