合并重叠的数字范围

Question

我需要把重叠的数字区域合并成一个区域。所以我有一个列表，其中有一些子列表，比如：

[[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。如果任何其他范围与此范围重叠，则此范围的最小值为最大值，如果没有其他范围重叠，则该方法应转到列表中的下一个范围，并尝试将其与重叠合并。你知道吗

我认为这是有道理的。你知道吗

Answer 1

使用间隔树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)])

Answer 2

如果我理解正确，你可以这样做：

from itertools import combinations
l = [[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]]


def any_items_overlap(l):

    # For each possible pair of lists in l
    for item1, item2 in combinations(l, 2):

        max1, min1 = item1
        max2, min2 = item2

        if min1 > max2 or max1 < min2:
            # no overlap so ignore this pair
            continue

        else:  # One of the combinations overlaps, so return them
            return item1, item2

    return None


while True:

    if not any_items_overlap(l):
        # No items overlapped - break the loop and finish
        print(l)
        break

    else:  # There are still overlaps
        item1, item2 = any_items_overlap(l)

        # Remove the items from the main list
        l.remove(item1)
        l.remove(item2)

        # Replace them with a merged version
        item_values = item1 + item2
        l.append([max(item_values), min(item_values)])
        # Start the loop again to check for any other overlaps

这将提供：

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

Answer 3

有一种天真的方法：

l = [[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]]
new_l = []
contained = False
for i,subl in enumerate(l):
    mini, maxi = min(subl), max(subl)
    for subl2 in l:
        if mini in range(subl2[1],subl2[0]+1):
            mini = subl2[1]
        elif maxi in range(subl2[1],subl2[0]+1):
            maxi = subl2[0]
    if len(new_l)>1:
        for subl3 in new_l:
            contained = False
            if mini in range(subl3[0],subl3[1]+1) or maxi in range(subl2[0],subl2[1]+1):
                contained = True
                break
    if contained == True: continue
    new_l.append([mini,maxi])
print(new_l)

输出：

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