在不使用集合的情况下减去两个范围的重叠部分

Question

不要使用集合！

我不能使用集合的原因是：

• 范围会太长。
• 会占用太多内存。
• 创建集合本身会花费太长时间。

---

只用范围的起止点，有没有什么好的方法来减去两个范围列表？

举个例子：

r1 = (1, 1000), (1100, 1200)  
r2 = (30, 50), (60, 200), (1150, 1300)

r1 - r2 = (1, 29), (51, 59), (201, 1000), (1100, 1149)

其他信息：

• r2 不一定要和 r1 重叠。
• r1 和 r2 之间不会有重叠的对，比如 r1 不会同时有 (0,30) 和 (10, 25) 这样的对。

谢谢。

Answer 1

这里有一个解决方案（除了这里提到的其他不同方案），就是使用区间树或线段树（它们其实是同一种东西）：

http://en.wikipedia.org/wiki/Segment_tree

http://en.wikipedia.org/wiki/Interval_tree

这样做的一个大优点是，使用同一段代码可以轻松进行任意布尔操作（不仅仅是减法）。在 de Berg 的书中有对这种数据结构的标准介绍。要对一对区间树执行任何布尔操作（包括减法），你只需将它们合并在一起。下面是一些（确实有点简单）用 Python 编写的代码，适用于不平衡的区间树。虽然它们是不平衡的，但合并树的时间不会受到影响，不过这里的树构建部分确实有点傻，最终的时间复杂度是平方级的（除非通过分区来执行合并，但我对此有些怀疑）。无论如何，代码如下：

class IntervalTree:
    def __init__(self, h, left, right):
        self.h = h
        self.left = left
        self.right = right

def merge(A, B, op, l=-float("inf"), u=float("inf")):
    if l > u:
        return None
    if not isinstance(A, IntervalTree):
        if isinstance(B, IntervalTree):
            opT = op
            A, B, op = B, A, (lambda x, y : opT(y,x))
        else:
            return op(A, B)
    left = merge(A.left, B, op, l, min(A.h, u))
    right = merge(A.right, B, op, max(A.h, l), u)
    if left is None:
        return right
    elif right is None or left == right:
        return left
    return IntervalTree(A.h, left, right)

def to_range_list(T, l=-float("inf"), u=float("inf")):
    if isinstance(T, IntervalTree):
        return to_range_list(T.left, l, T.h) + to_range_list(T.right, T.h, u)
    return [(l, u-1)] if T else []

def range_list_to_tree(L):
    return reduce(lambda x, y : merge(x, y, lambda a, b: a or b), 
        [ IntervalTree(R[0], False, IntervalTree(R[1]+1, True, False)) for R in L ])        

我写这段代码的时候比较快，测试也不多，所以可能会有一些错误。另外请注意，这段代码可以处理任意布尔操作，而不仅仅是差集（你只需将它们作为参数传递给合并函数中的 op）。评估这些操作的时间复杂度是线性的，和输出树的大小有关（这也和结果中的区间数量相同）。举个例子，我在你提供的案例上运行了它：

#Example:
r1 = range_list_to_tree([ (1, 1000), (1100, 1200) ])
r2 = range_list_to_tree([ (30, 50), (60, 200), (1150, 1300) ])
diff = merge(r1, r2, lambda a, b : a and not b)
print to_range_list(diff)

得到了以下输出：

[(1, 29), (51, 59), (201, 1000), (1100, 1149)]

这似乎和你预期的结果一致。现在，如果你想进行其他布尔操作，这里是如何使用同一个函数来实现的：

#Intersection
merge(r1, r2, lambda a, b : a and b)

#Union
merge(r1, r2, lambda a, b : a or b)

#Xor
merge(r1, r2, lambda a, b : a != b)

Answer 2

这个问题挺有意思的！

我觉得这个方法是对的，而且比较简洁。它应该能处理各种重叠的范围，但它假设范围是合理的（也就是说，[x, y) 里 x < y）。为了简单起见，它使用了 [x, y) 这种范围表示法。这个方法的基础是观察到其实只有六种可能的排列方式（结果在括号里）。

编辑：我找到了一种更简洁的表示方法：

(s1 e1)  s2 e2
(s1 s2)  e1 e2
(s1 s2) (e2 e1)

 s2 e2  (s1 e1)
 s2 s1  (e2 e1)
 s2 s1   e1 e2 ()

给定一个排好序的端点列表，如果 endpoints[0] == s1，那么前两个端点应该在结果里。如果 endpoints[3] == e1，那么最后两个端点应该在结果里。如果都不是，那就不应该有结果。

我还没有做很多测试，所以可能会有错误。如果你发现了问题，请告诉我！

import itertools

def range_diff(r1, r2):
    s1, e1 = r1
    s2, e2 = r2
    endpoints = sorted((s1, s2, e1, e2))
    result = []
    if endpoints[0] == s1 and endpoints[1] != s1:
        result.append((endpoints[0], endpoints[1]))
    if endpoints[3] == e1 and endpoints[2] != e1:
        result.append((endpoints[2], endpoints[3]))
    return result

def multirange_diff(r1_list, r2_list):
    for r2 in r2_list:
        r1_list = list(itertools.chain(*[range_diff(r1, r2) for r1 in r1_list]))
    return r1_list

测试过：

>>> r1_list = [(1, 1001), (1100, 1201)]
>>> r2_list = [(30, 51), (60, 201), (1150, 1301)]
>>> print multirange_diff(r1_list, r2_list)
[(1, 30), (51, 60), (201, 1001), (1100, 1150)]

Answer 3

这个interval包可能包含你所需要的所有功能。

from interval import Interval, IntervalSet
r1 = IntervalSet([Interval(1, 1000), Interval(1100, 1200)])
r2 = IntervalSet([Interval(30, 50), Interval(60, 200), Interval(1150, 1300)])
print(r1 - r2)

>>> [1..30),(50..60),(200..1000],[1100..1150)