多个范围的联合 [英] Union of multiple ranges

问题描述

我有这些范围:

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).这是正确处理这种情况的新版本:

As @CentAu correctly notices, [(2,4), (1,6)] would return (1,4) instead of (1,6). Here is the new version with correct handling of this case:

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

这篇关于多个范围的联合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！