algorithm - 找到构成整体的所有可能重叠的片段集？

Question

假设 space = [0, 100] 并且给出了多个间隔。

这些间隔是空间的碎片，并且可能重叠。

[0, 30], [0, 20], [10, 40], [30, 50], [50, 90], [70, 100]

是一组区间。

从上述集合中选择的跨越整个空间的一组区间的示例是:

[0, 30], [10, 40], [30, 50], [50, 90], [70, 100]

另一个例子是

[0, 30], [30, 50], [50, 90], [70, 100]

这是前面示例中没有 [10, 40] 的集合。

我想找到这些间隔集的所有组合，以计算每个间隔的成本并找到成本最低的那个。

from operator import itemgetter
import collections

tmp = [(0, 30), (0, 20), (10, 40), (30, 50), (50, 90), (70, 100), ]
aa = sorted(tmp, key=itemgetter(1)) # sort with respect to 1st elem
a = set(aa)
space = 100
d_conn = 15
RTT = d_conn*2
bandwidth = 10

def get_marginal_cost(fragment):
    return RTT + (fragment[1] - fragment[0])/bandwidth

def dfs(a, start, path=None):
    if path is None:
        path = [start, ]
    if start[1] == space:
        yield path
    for frgmt in a - set(path):
        l = frgmt[0]
        r = frgmt[1]
        if start[0] < l <= start[1] <= r:
#        if l <= start[1] <= r:
            yield dfs(a, frgmt, path + [frgmt, ])

for z in a:
    if z[0] == 0:
        for output in list(dfs(a, z)):
            for outpu in list(output):
                for outp in list(outpu):
                    for out in list(outp):
                        for ou in list(out):
                            print list(ou)

到目前为止，这是我的尝试，但我无法完成。

特别是，我希望在不使用 Python 中的 yield 功能的情况下完成此操作，因为我不熟悉它并且我可能想在 C++ 中实现它。

谁能帮我写一个解决这个问题的工作程序？

谢谢。

Answer 1

Is it really necessary to build a tree just to find the minimum cost?

可能不会(假设您当前未指定的成本函数显示最优子结构)。

对于线性成本函数，以下经典算法的运行时间为 O(n log n)，其中 n 是间隔数。初始化从 mid 到覆盖 [0, mid] 的成本的排序映射。最初，此映射有一个条目，0 -> 0。按右端点对区间进行排序，并按如下顺序处理它们。要处理 [a, b]，找到映射条目 mid -> cost 使得 mid >= a 尽可能小。 (如果不存在这样的条目，则继续。)让成本'=成本+成本([a，b])，其中成本([a，b])未指定但始终为正。本地图中最后一个条目的成本大于或等于成本'时，将其删除。插入 b -> 成本'。最后，查找 end 的后继，其中 [0, end] 是要覆盖的空间。

即使您的成本函数不是线性的，因为它是总区间长度和区间数的(可能是单调的)函数，我们也可以获得 O(n^2) 时间的算法，而不是仅仅记住每个中点一个成本，记住 0 到 n 之间的每个整数，使用指定间隔数的解决方案的成本。