algorithm - 查找具有非重叠区域的所有组合

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)