如何从跨距列表中获得所有最大的非重叠跨距集

Question

我似乎找不到一种在标题中编写算法的方法，而不需要以某种方式整理结果。在

为了说明我想要什么：

all_spans = [(0, 5), (2, 7), (5, 8), (6, 10), (9, 10), (11, 15)]
possible_sets = [
    {(0, 5), (5, 8), (9, 10), (11, 15)},
    {(2, 7), (9, 10), (11, 15)},
    {(0, 5), (6, 10), (11, 15)}
]
not_possible = [
    {(0, 5), (5, 8), (6, 10), (11, 15)},  # has overlaps
    {(5, 8), (9, 10), (11, 15)}           # not maximal w.r.t possible_sets[0]
]

我目前的实施或多或少是这样的：

^{pr2}$

但它产生了非最大跨距，我宁愿一开始就不想创建。在

>>> for s in combine(all_spans, set()):
...     print(sorted(s))
[(9, 10), (11, 15)]
[(6, 10), (11, 15)]
[(5, 8), (9, 10), (11, 15)]
[(9, 10), (11, 15)]
[(6, 10), (11, 15)]
[(2, 7), (9, 10), (11, 15)]
[(0, 5), (9, 10), (11, 15)]
[(0, 5), (6, 10), (11, 15)]
[(0, 5), (5, 8), (9, 10), (11, 15)]

有没有其他方法可以避免这种行为？我在“间隔重叠”和“活动调度”这两个关键词下发现了类似的问题，但它们似乎都没有提到这个特定的问题。在

Answer 1

这是一个简单的（？）图形问题。制作一个有向图，其中每个跨度是一个节点。如果span B直到span A结束才开始，则存在边AB（从节点A到节点B）iff A[1]<；=B[0]。你的图表看起来像

Node    =>  Successors
(0, 5)  =>  (5, 8), (6, 10), (9, 10), (11, 15)
(2, 7)  =>  (9, 10), (11, 15)
(5, 8)  =>  (9, 10), (11, 15)
(6, 10) =>  (11, 15)
(9, 10) =>  (11, 15)

现在，问题简化为简单地找到通过图的最长路径，包括连接。在

考虑到问题的线性度，找到一个最大解比较容易：在每一步中，选择具有最快结束时间的后续节点。分步骤：

1. 首先，所有节点都可用。结束时间最快的是（0,5）。在
2. 最早结束的（0,5）的继承者是（5,8）。在
3. （5，8）的继承人。。。是（9，10）
4. 。。。最后加上（11，15）

请注意，这并不需要一个图；只需要一个您愿意通过第一个子元素或第二个子元素引用的结构。在

解的长度是4，你已经知道了。在

你能从这里取吗？在