合并重叠的数字范围

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。如果任何其他范围与此范围重叠，则该范围会将其最小或最大值添加到该范围中，当没有其他范围与之重叠时，该方法应该转到列表中的下一个范围，并尝试将其与其重叠合并。我希望这有意义。

- XelaGreb

---

添加* 最小值或最大值* - XelaGreb

请发布您期望的输出以及您目前为实现该输出所做的尝试。 - user2390182

我是Python的新手，已经困扰于这个问题很长时间了，因为我无法理解其逻辑。我没有尝试过，这就是我首先寻求帮助的原因。我也已经描述了我期望的输出结果。非常感谢您的理解和帮助。 - XelaGreb

你只是说“将变为76到83”。这是否意味着你的输出应该是[[76, 83], ...]？原始数据中的数对是否总是按降序排列，而你期望的结果数对是否应该按升序排列？ - user2390182

首先，感谢您的回应！是的，重点是优化/压缩列表，以便合并重叠的范围。因此，这两个将变成一个，如果有任何其他重叠它们的也将被添加，因此3个子列表将变为1个。列表的顺序没有指定，因此可以按降序或升序排列。 - XelaGreb

Answer 1

使用IntervalTree 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)])

- Cireo

---

谢谢您的解释和帮助！ - XelaGreb

想要注意的是，如果您使用大量间隔，这将更加可靠。逻辑的定制版本将允许额外的改进，因为您只想要合并值，但它应该比组合或嵌套的for循环快~|列表大小|倍。 - Cireo

收到！再次感谢您提供的额外信息！ - XelaGreb

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

- seymourgoestohollywood

---

非常感谢，解决方案起作用了！现在我要离开一周，因为我有点笨，需要很多时间来理解这段代码...尽管如此，非常感激！ - XelaGreb

没问题 - 我已经添加了一些注释来解释正在发生的事情。 - seymourgoestohollywood

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

- Sayandip Dutta