Combine overlapping ranges of numbers

user_12253939 0
Viewed 1294

I need to combine overlapping ranges of numbers into single range. So I have a list with sub-lists of something like:

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

So from 83 to 77 is overlapping 82 to 76 and will become 76 to 83. If any other ranges overlap this range would ad it's minimum of maximum to this range, and when there no others that overlap then the method should go to the next one in the list and try to merge that with it's overlappings.

I hoop this makes sense.

range numbers overlap python
3 Answers

Use an IntervalTree https://en.wikipedia.org/wiki/Interval_tree

There is an implementation available in 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)

note that I had to make your points be (start, end) instead of (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)])

is merged to

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

and with strict=False allowing touching intervals to be merged

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

If I understand you correctly, you can do this:

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

This gives:

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

Here's one naive way:

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)

Output:

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