python 求n個區(qū)間范圍，并集的算法

python有個區(qū)間處理庫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]

舉個簡單的方法：首先計算出任意兩個集合的交集，然后推廣到 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):
    """
    測試交集算法函數(shù) f

    # 測試數(shù)據(jù)
      * 元素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)

以此類推，你可以實現(xiàn)并集算法。

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

# -*- 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