Объедините перекрывающиеся диапазоны чисел

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

Если я вас правильно понимаю, вы можете сделать это:

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 2

Вот один наивный способ:

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

Answer 3

Используйте 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)])