小编典典

Python间隔相交

algorithm

我的问题如下:

具有间隔列表的文件:

1 5
2 8
9 12
20 30

和一系列

0 200

我想做一个这样的交集,将报告给定范围内我的间隔之间的位置[开始结束]。

例如:

8 9
12 20
30 200

除了任何想法如何咬合这一点之外,阅读一些关于优化的想法也将很高兴,因为与往常一样,输入文件将非常庞大。


阅读 293

收藏
2020-07-28

共1个答案

小编典典

只要间隔按起点排序,此解决方案就可以工作,并且不需要创建与总范围一样大的列表。

with open("0.txt") as f:
    t=[x.rstrip("\n").split("\t") for x in f.readlines()]
    intervals=[(int(x[0]),int(x[1])) for x in t]

def find_ints(intervals, mn, mx):
    next_start = mn
    for x in intervals:
        if next_start < x[0]:
            yield next_start,x[0]
            next_start = x[1]
        elif next_start < x[1]:
            next_start = x[1]
    if next_start < mx:
        yield next_start, mx

print list(find_ints(intervals, 0, 200))

输出:

(以您提供的示例为例)

[(0, 1), (8, 9), (12, 20), (30, 200)]
2020-07-28