找到具有非重叠区域的所有组合

Question

在一个超区域S中，有k个小的子区域。数量 k 可以达到 200。子区域之间可以有重叠。我有数百万个区域S.

对于每个超级区域，我的目标是找出所有包含 2 个或更多非重叠子区域的组合。

这是一个例子：

超级区域：1-100

分区：1-8、2-13、9-18、15-30、20-35

目标：

组合 1: 1-8, 9-18

组合 2: 1-8, 20-35

组合 3：1-8、9-18、20-35

组合 4：1-8、15-30

...

Answer 1

子集的数量可能是指数级的（最大 2^k），所以用递归遍历所有可能的独立子集并没有错。我使用了下一个可能区间的线性搜索，但值得利用二进制搜索。

def nonovl(l, idx, right, ll):
    if idx == len(l):
        if ll:
            print(ll)
        return

    #find next non-overlapping interval without using l[idx]
    next = idx + 1  
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll)

    #find next non-overlapping interval after using l[idx]
    next = idx + 1
    right = l[idx][1]
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll + str(l[idx]))

l=[(1,8),(2,13),(9,18),(15,30),(20,35)]
l.sort()
nonovl(l, 0, -1, "")

(20, 35)
(15, 30)
(9, 18)
(9, 18)(20, 35)
(2, 13)
(2, 13)(20, 35)
(2, 13)(15, 30)
(1, 8)
(1, 8)(20, 35)
(1, 8)(15, 30)
(1, 8)(9, 18)
(1, 8)(9, 18)(20, 35)

找到具有非重叠区域的所有组合

find all combinations with non-overlapped regions

algorithm

intervals

interval-tree