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

Question

假设我有一个范围（部分）和一个要排除的范围的附加列表，用元组（start，end）表示：

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

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

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

^{pr2}$

这是主范围，不包括第二个范围列表。在

谢谢！在

编辑：

实际上，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

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

Answer 3

有人这么想？在

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))

编辑：根据pacoh.comment添加if子句进行更正

^{pr2}$