pythonnumbersrangeoverlap

Combine overlapping ranges of numbers


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.


Solution

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