如何在Python中从另一个范围中排除一个范围？

Question

假设我有一个范围（section）和一个额外的要排除的范围列表，由元组（start，end）表示：

section=(1, 100) #Range from 1 to 100

toexclude=[(10,15),(40,50),(80,83)]  #3 sub-ranges

我正在寻找一种有效的算法，从这两个输入中返回一个新的范围列表，如：

[(1,9),(16,39),(51,79),(84,100)]

这是引出第二个范围列表的主范围。

谢啦！

编辑：

实际上，deceze关于使用intervaltree的建议似乎很有趣。有几行：

from intervaltree import Interval, IntervalTree
t=IntervalTree()
t[1:100]="main"
t.chop(10,15)
t.chop(40,50)
t.chop(80,83)
t
IntervalTree([Interval(1, 10, 'main'), Interval(15, 40, 'main'), Interval(50, 80, 'main'), Interval(83, 100, 'main')])

显然，间隔被视为已关闭，但这是一个小问题。

Answer 1

section=(1, 100) #Range from 1 to 100

toexclude=[(10,15),(40,50),(80,83)]  #3 sub-rang

list1 = []
list2 = [section[0]]
[list1.append(x[0]-1) for x in toexclude]
[list2.append(x[1]+1) for x in toexclude]
list1.append(section[1])

print list(zip(list2, list1)
# [(1, 9), (16, 39), (51, 79), (84, 100)]

Answer 2

有人这样想吗？

start, end = section

this_start = start
result = []
for exc_start, exc_end in toexclude:
    this_end = exc_start - 1
    result.append((this_start, this_end))
    this_start = exc_end + 1

result.append((this_start, end))

编辑：添加了根据Paco H.注释进行更正的if条款

start, end = section

this_start = start
result = []
for exc_start, exc_end in toexclude:
    if this_end == start:
        start = exc_end + 1
    else:
        this_end = exc_start - 1
        result.append((this_start, this_end))
        this_start = exc_end + 1

if this_end <= end:
    result.append((this_start, end))

Answer 3

section=(1, 100) #Range from 1 to 100

toexclude=[(10,15),(40,50),(80,83)]  #3 sub-ranges


rangelists = [x for excRange in toexclude for x in range(excRange[0], excRange[1] + 1)]
first, last = section[0], section[0]
out_ranges = []
for x in range(section[0],section[1] + 1):
    if x not in rangelists:
        if first == 'unset':
            first = x
        last = x
    elif x in rangelists:
        if last == x - 1:
            out_ranges.append((first, last))
            first = 'unset'
        else:
            continue
if first != 'unset':
    out_ranges.append((first, last))

print out_ranges