多范围的python联合

Question

我有这些范围:

7,10
11,13
11,15
14,20
23,39

我需要执行重叠范围的并集以给出不重叠的范围,因此在示例中:

7,20
23,39

我在Ruby中完成了这个,我已经在数组中推动了范围的开始和结束并对它们进行了排序,然后执行重叠范围的并集.有什么快速的方法在Python中执行此操作？

谢谢

Answer 1

让我们说,(7, 10)并(11, 13)导致(7, 13):

a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
b = []
for begin,end in sorted(a):
    if b and b[-1][1] >= begin - 1:
        b[-1] = (b[-1][0], end)
    else:
        b.append((begin, end))

b 就是现在

[(7, 20), (23, 39)]

编辑:

正如@CentAu正确注意到的那样,[(2,4), (1,6)]将返回(1,4)而不是(1,6).以下是正确处理此案例的新版本:

a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
b = []
for begin,end in sorted(a):
    if b and b[-1][1] >= begin - 1:
        b[-1][1] = max(b[-1][1], end)
    else:
        b.append([begin, end])

Answer 2

老问题.但是我想为将来的参考添加这个答案. sympy可以用来实现间隔的结合:

from sympy import Interval, Union
def union(data):
    """ Union of a list of intervals e.g. [(1,2),(3,4)] """
    intervals = [Interval(begin, end) for (begin, end) in data]
    u = Union(*intervals)
    return [list(u.args[:2])] if isinstance(u, Interval) \
       else list(u.args)

如果输出Union超过两个间隔是一个Union对象,而当有一个间隔时,输出是一个Interval对象.这就是回归线的原因if statement.

例子:

In [26]: union([(10, 12), (14, 16), (15, 22)])
Out[26]: [[10, 12], [14, 22]]

In [27]: union([(10, 12), (9, 16)])
Out[27]: [[9, 16]]