多个范围的并集

问题描述

我有这些范围:

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

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

I need to perform a union of the overlapping ranges to give ranges that are not overlapping, so in the example:

7,20
23,39

我已经在 Ruby 中完成了这项工作，我在数组中推送了范围的开始和结束并对它们进行排序，然后执行重叠范围的联合.在 Python 中有什么快速的方法吗?

I've done this in Ruby where I have pushed the start and end of the range in array and sorted them and then perform union of the overlapping ranges. Any quick way of doing this in Python?

推荐答案

比方说，(7, 10) 和 (11, 13) 结果为 (7, 13):

Let's say, (7, 10) and (11, 13) result into (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])