多个范围的并集

编程基础网 Python问题

2022-01-01

Union of multiple ranges(多个范围的并集)

本文介绍了多个范围的并集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有这些范围:

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

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


                        这篇关于多个范围的并集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！