合并重叠的数字范围

我需要将重叠的数字范围合并为单个范围。所以我有一个包含子列表的列表，例如：

[[83,77],[103,97],[82,76],[101,95],[78,72],[97,91],[72,66],[89,83],[63,57],[78,72],[53,47],[65,59],[41,35],[50,44],[28,22],[34,28],[14,8],[16,10]]

因此，从 83 到 77 与 82 到 76 重叠，并且将变为 76 到 83。如果任何其他范围重叠此范围，则将其最小值或最大值添加到此范围，并且当没有其他重叠时，该方法应转到下一个范围并尝试将其与其重叠部分合并。

我希望这是有道理的。

使用区间树https://en.wikipedia.org/wiki/Interval_tree https://en.wikipedia.org/wiki/Interval_tree

python 中有一个可用的实现：

pip install intervaltree

import intervaltree

intervals = [
    [77, 83],
    [97, 103],
    [76, 82],
    [95, 101],
    [72, 78],
    [91, 97],
    [66, 72],
    [83, 89],
    [57, 63],
    [72, 78],
    [47, 53],
    [59, 65],
    [35, 41],
    [44, 50],
    [22, 28],
    [28, 34],
    [8, 14],
    [10, 16],
]

tree = intervaltree.IntervalTree.from_tuples(intervals)

print(tree)
tree.merge_overlaps()
print(tree)
tree.merge_overlaps(strict=False)
print(tree)

请注意，我必须表达你的观点(start, end)代替(end, start).

IntervalTree([Interval(8, 14), Interval(10, 16), Interval(22, 28), Interval(28, 34), Interval(35, 41), Interval(44, 50), Interval(47, 53), Interval(57, 63), Interval(59, 65), Interval(66, 72), Interval(72, 78), Interval(76, 82), Interval(77, 83), Interval(83, 89), Interval(91, 97), Interval(95, 101), Interval(97, 103)])

被合并到

IntervalTree([Interval(8, 16), Interval(22, 28), Interval(28, 34), Interval(35, 41), Interval(44, 53), Interval(57, 65), Interval(66, 72), Interval(72, 83), Interval(83, 89), Interval(91, 103)])

与strict=False允许合并触摸间隔

IntervalTree([Interval(8, 16), Interval(22, 34), Interval(35, 41), Interval(44, 53), Interval(57, 65), Interval(66, 89), Interval(91, 103)])