在范围值列表中查找间隙

下面是一个简洁的解决方案,使用 itertools.chain union-of-ranges 算法。

from itertools import chain

def range_gaps(a, b, ranges):
    ranges = sorted(ranges)
    flat = chain((a-1,), chain.from_iterable(ranges), (b+1,))
    return [[x+1, y-1] for x, y in zip(flat, flat) if x+1 < y]

拿 range_gaps(1, 100, [[10, 50], [90, 100]])

• 首先对范围进行排序,以防它们尚未按顺序排列。如果保证它们处于有序状态,则不需要此步骤。
• 然后 flat 0, 10, 50, 90, 100, 101
• 自从 延迟计算并通过迭代消耗, zip(flat, flat) 给出一个成对序列,如 (0, 10), (50, 90), (100, 101)
• 所需的范围如下 (1, 9), (51, 89) (100, 101) 应给出一个空范围,以便丢弃。

该代码将逐个获取所有子范围,并将与原始完整范围和之前的子范围进行比较,以找到缺失的范围。

[start,end]=[1,100]
chunks=[[25,31],[7,15],[74,83]]

print([r for r in [[start,chunks[0][0]-1] if start!=chunks[0][0] else []] + [[chunks[i-1][1]+1, chunks[i][0]-1] for i in range(1,len(chunks))]+[[chunks[-1][1]+1,end] if end!=chunks[-1][1] else []] if r])

输入

[1,100]
[[7,15],[25,31],[74,83]]

[[1, 6], [16, 24], [32, 73], [84, 100]]

如果不能保证子范围的递增顺序。您可以在下面的行中包含排序块。

chunks.sort(key=lambda x: x[0])

这是一种通用解决方案:

def gap(N, ranges):
    ranges=[(min1, max1), (min2, (max2), ......, (minn, maxn)]
    
    original=set(range(N))
           
    for i in ranges:
        original=original-set(range(i[0], i[1]))

    return original