多个范围的并集

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])