python 求n个区间范围，并集的算法

Question

有n个有序的集合，集合的每个元素都是一段范围，求n个集合的交集，例如n=3，集合{[2,4],[9,13]}和{[6,12]}的并集为{[2,4],[6,13]}，请问用python怎么实现

Answer 1

python有个区间处理库interval

from interval import Interval, IntervalSet

data = [(2, 4), (9, 13), (6, 12)]

intervals = IntervalSet([Interval.between(min, max) for min, max in data])
print [(_.lower_bound, _.upper_bound) for _ in intervals]

Answer 2

第一步排序，第二步遍历。

# -*- coding: utf-8 -*-

data = [
    [1,2],
    [2,3],
    [1,6],
    [1,3],
    [3,7],
    [3,6],
    [3,8],
    [3,7],
    [10,12],
    [110,290],
    [50,60],
    [49,55],
]

def sort(a, b):
    if a[0] > b[0]: return 1
    if a[0] < b[0]: return -1
    if a[1] > b[1]: return 1
    if a[1] < b[1]: return -1
    return 1

data.sort(sort)
result = []

for a, b in data:
    if not result:
        result.append([a, b])
        continue

    la, lb = result[-1]
    if la <= a <= lb and b > lb:
        result[-1][1] = b
    if a > lb:
        result.append([a, b])

print result

Answer 3

举个简单的方法：首先计算出任意两个集合的交集，然后推广到 N 个集合。

示例代码如下

# -*- coding: utf-8 -*-
from functools import reduce


def intersection(range_a, range_b):
    """ 返回两集合的交集，None 代表空集。"""
    if not (range_a and range_b):
        return None
    lower_a, upper_a = range_a
    lower_b, upper_b = range_b
    if lower_b < lower_a:
        if upper_b < lower_a:
            return None
        if upper_b < upper_a:
            return (lower_a, upper_b)
        return tuple(range_a)
    if lower_b < upper_a:
        if upper_b < upper_a:
            return tuple(range_b)
        return (lower_b, upper_a)
    return None


def intersectionN(ranges):
    """ 返回 N 个集合的交集，None 代表空集。"""
    return reduce(intersection, ranges)


def _test_intersection_algorithm(f):
    """
    测试交集算法函数 f

    # 测试数据
      * 元素i：  输入值
      * 元素i+1: 期望输出值

    # 测试方法
      输入值的第一个集合 (3,6) 固定不变，以输入值第二个集合 (x,y) 的位置进行分组：
      1. x < 3,     y < 3
      2. x < 3, 3 < y < 6
      3. x < 3, 6 < y

      4. 3 < x < 6,     y < 6
      5. 3 < x < 6, 6 < y

      6. 6 < x, 6 < y
    """
    test_records = [
        [(3, 6), (1, 2)],   None,
        [(3, 6), (1, 4)],   (3, 4),
        [(3, 6), (1, 7)],   (3, 6),

        [(3, 6), (4, 5)],   (4, 5),
        [(3, 6), (4, 7)],   (4, 6),

        [(3, 6), (7, 9)],   None,
    ]

    for i in range(len(test_records)/2):
        input_set = test_records[2*i]
        expected = test_records[2*i+1]
        assert f(input_set) == expected, (
            'input: %s, expected: %s' % (input_set, expected))


def test_intersection():
    # 使用 pytest 进行测试。
    _test_intersection_algorithm(intersectionN)

以此类推，你可以实现并集算法。