28

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

问题是间隔重叠，重叠间隔中我只能使用一个。这是一个例子。

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

编辑：间隔没有特别的顺序。

4

6 回答 6

26

这是间隔调度的加权变体；可以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)最坏情况下的性能）或其他一系列二进制搜​​索来查找最右边的索引。

哎呀，我又说基因了吗？我的意思是间隔。

相关问题

于 2010-07-14T09:58:39.467 回答
4

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

首先，您按照起点对所有区间进行排序，然后从头到尾迭代。对于列表中的每个项目，您选择从该点到最后一个的最大总和max(S[i]+S[j], S[i+1])，其中 i 是您所在的项目，j 是您的项目之后的第一个非重叠条目的项目（即第一个项目其开始大于当前项的结束）。为了加快算法速度，您希望存储每个元素的最大部分和 S[j]。

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

 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

这是本文中算法的改编版，但不幸的是，它没有很好的 O(n) 运行时间。每个条目与下一个条目重叠的退化列表将导致它为 O(n^2)。

于 2010-07-14T07:55:32.740 回答
0

也许可以使用类似这个答案的方法，至少对于那个问题是O(n) 。这意味着对间隔进行一次迭代，并仅跟踪那些仍然可能导致最佳最终解决方案的间隔组合。

于 2010-07-14T03:49:50.933 回答
0

听起来像是背包问题的变体。您可能会在寻找这些解决方案时找到一些灵感。

我们在谈论多少个间隔？如果它只有大约 5 个（如您的示例中所示），那么尝试每种组合可能更实用。如果它更多，那么一个理想解决方案的近似值会做吗？同样，背包解决方案（例如 George Dantzig 的贪婪逼近算法）可能是一个很好的起点。

于 2010-07-14T03:52:21.283 回答
0

我想了一会儿，想出了一些东西。

区间树提供了一种查找与给定区间重叠的所有区间的有效方法。遍历整个区间，我们可以找到给定区间的所有重叠区间。一旦我们有了这些，我们就可以找到得分最高的区间，存储它并继续前进。

构建树需要 O(N Log N) 时间，查找需要 O(Log N) 时间。因为我们查找所有元素，所以解决方案变为 O(N Log N)。

但是，如果我们遇到类似上述示例的情况，其中一组中的最高得分区间减少了总数，那么算法就会失败，因为我们无法知道不应该事先使用最高得分区间。解决这个问题的明显方法是在我们不确定的情况下计算两个（或全部）总数，但这会使我们回到潜在的 O(N^2) 或更差的解决方案。

于 2010-07-14T15:39:06.230 回答
0

我认为我们可以使用这种递归......

S[i]表示每个区间的得分
Interval[i]表示所有区间

ResMax[i] = max(ResMax[i-1] + S[i] //if i is included
           ,max(R[i-1],S[i]) 
         )

我没有经过彻底检查，但我相信它应该可以工作。

于 2011-10-21T03:32:32.483 回答