python - 独特的范围集，在需要时合并

Question

是否有一种数据结构可以维护一组唯一的范围，合并添加的连续或重叠范围？我需要跟踪哪些范围已被处理，但这可能以任意顺序发生。例如:

range_set = RangeSet() # doesn't exist that I know of, this is what I need help with

def process_data(start, end):
    global range_set
    range_set.add_range(start, end)
    # ...

process_data(0, 10)
process_data(20, 30)
process_data(5, 15)
process_data(50, 60)

print(range_set.missing_ranges())
# [[16,19], [31, 49]]

print(range_set.ranges())
# [[0,15], [20,30], [50, 60]]

请注意，重叠或连续的范围会合并在一起。做这个的最好方式是什么？我查看了 bisect 模块的使用，但它的使用似乎不是很清楚。

Answer 1

另一种方法是基于sympy.sets .

>>> import sympy as sym
>>> a = sym.Interval(1, 2, left_open=False, right_open=False)
>>> b = sym.Interval(3, 4, left_open=False, right_open=False)
>>> domain = sym.Interval(0, 10, left_open=False, right_open=False)
>>> missing = domain - a - b
>>> missing
[0, 1) U (2, 3) U (4, 10]
>>> 2 in missing
False
>>> missing.complement(domain)
[1, 2] U [3, 4]