非重叠区间的贪婪选择

Question

我试图实现this paper（GBDP策略，“匹配距离”）中描述的算法，需要一点澄清。

基本上，问题是我有一个项目列表，其中每个项目有一个长度和间隔（它实际上是两个区间，但它是相同的想法）。

ID LENGTH START END 
1  1000  1  1000 
2  20000  5  20005 
3  20  30500 30520 
4  500  30500 31000 
5  200  900  1100  

目标是找到具有非重叠范围的项目子集。在论文中，他们说他们首先由长度

ID LENGTH START END 
2  20000  5  20005 
1  1000  1  1000 
4  500  30500 31000 
5  200  900  1100 
3  20  30500 30520 

对项目进行排序，然后进行“贪婪地选择[项目]具有非重叠的时间间隔的一个子集”。这是我困惑的地方。我知道一个贪婪的算法是什么，但我不确定这里的作者是什么意思。我猜想可能是他们只是通过清单，只保留那些不与上面那些重叠的项目。

ID LENGTH START END 
2  20000  5  20005 
4  500  30500 31000 
5  200  900  1100 
3  20  30500 30520 

注意，使用这种方法，结果仍然包括具有重叠范围的项目（4和3）。

我设法在Perl中轻松实现这种方法，但我想这可能不是作者的意图。他们的意思是保留与任何以上的其他项目不重叠的项目？如果有人在这种情况下解释了“贪婪选择”的含义，我会很感激。

Answer 1

你几乎到最后是正确的（并且不是，你提出正确的解释作为选项）。

首先，正如你所说，从而使长度减少排序的事情：

ID LENGTH START END 
2  20000  5  20005 
4  500  30500 31000 
5  200  900  1100 
3  20  30500 30520 

现在我们贪婪，只要他们不前几次的任何选择了冲突选择的时间间隔。因此，选定的组最初为空，

1. 最初，2是我们可以做出的最贪婪的选择（长度为20000）。它不冲突，所以我们将它添加到所选集合中。
2. 同上4和5.选择的集合现在是{2,4,5}。
3. 下一个贪婪（以及简单剩余）的选择是3.因为它与的任何冲突，即4，我们不能使用它。

因此，结果是{2,4,5}。

---

仅供参考，这与计算机科学中一个众所周知的问题 - 区间调度密切相关。如果您尝试优化总数的数字的匹配项，而不是总数长度的匹配项，您sort by end position and greedily choose。