bioinf80 bioinf80 - 4 months ago 20
Python Question

python union of multiple ranges

I have these ranges:

7,10
11,13
11,15
14,20
23,39


I need to perform a union of the overlapping ranges to give ranges that are not overlapping, so in the example:

7,20
23,39


I've done this in Ruby where I have pushed the start and end of the range in array and sorted them and then perform union of the overlapping ranges. Any quick way of doing this in Python?

Thanks

Answer

Let's say, (7, 10) and (11, 13) result into (7, 13):

a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
b = []
for begin,end in sorted(a):
    if b and b[-1][1] >= begin - 1:
        b[-1] = (b[-1][0], end)
    else:
        b.append((begin, end))

b is now

[(7, 20), (23, 39)]

EDIT:

As @CentAu correctly notices, [(2,4), (1,6)] would return (1,4) instead of (1,6). Here is the new version with correct handling of this case:

a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
b = []
for begin,end in sorted(a):
    if b and b[-1][1] >= begin - 1:
        b[-1][1] = max(b[-1][1], end)
    else:
        b.append((begin, end))
Comments