Overlap in python

[Jay Bird]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

I've tried various methods, which all fail. Does anyone have an idea
how to do this?

Thank you very much!
Jay

 

[Marcus Wanner]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list.  For example, here would be my input:

part name   location
a                  5-9
b                  7-10
c                  3-6
d                  15-20
e                  18-23

And here is what I need for an output:
part name   location
c.a.b            3-10
d.e               15-23

I've tried various methods, which all fail.  Does anyone have an idea
how to do this?

Thank you very much!
Jay

Just take all the values, put them in a list, and use min() and max().
For example:

import string

def makelist(values):
values = string.replace(values, ' ', '')
listofvaluepairs = string.split(values, ',')
listofvalues = []
for pair in listofvaluepairs:
twovalues = string.split(pair, '-')
listofvalues.append(int(twovalues[0]))
listofvalues.append(int(twovalues[1]))
return listofvalues

values = '5-9, 7-10, 3-6'
values = makelist(values)
print('Values: %d-%d' %(min(values), max(values)) )

Marcus

 

[Ann]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list.  For example, here would be my input:

part name   location
a                  5-9
b                  7-10
c                  3-6
d                  15-20
e                  18-23

And here is what I need for an output:
part name   location
c.a.b            3-10
d.e               15-23

I've tried various methods, which all fail.  Does anyone have an idea
how to do this?

Thank you very much!
Jay

Just take all the values, put them in a list, and use min() and max().
For example:

import string

def makelist(values):
    values = string.replace(values, ' ', '')
    listofvaluepairs = string.split(values, ',')
    listofvalues = []
    for pair in listofvaluepairs:
        twovalues = string.split(pair, '-')
        listofvalues.append(int(twovalues[0]))
        listofvalues.append(int(twovalues[1]))
    return listofvalues

values = '5-9, 7-10, 3-6'
values = makelist(values)
print('Values: %d-%d' %(min(values), max(values)) )

Marcus

Thank you for your help, this is a very nice program but it does not
address the issue that I have values that do not overlap, for example
'c' and 'd' do not overlap in the above example and thus I would not
want to output 3-20 but the individual positions instead. In
addition, my inputs are not ordered from smallest to largest, thus I
could have a situation where a=5-9, b=15-20, c=7-10, etc., and I would
still want an output of: a.c = 5-10, b=15-20. I apologize for the
complication.

Thank you again!

Jay

 

[Marcus Wanner]

Hi everyone,
I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:
part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23
And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23
I've tried various methods, which all fail. Does anyone have an idea
how to do this?
Thank you very much!
Jay

Just take all the values, put them in a list, and use min() and max().
For example:

import string

def makelist(values):
values = string.replace(values, ' ', '')
listofvaluepairs = string.split(values, ',')
listofvalues = []
for pair in listofvaluepairs:
twovalues = string.split(pair, '-')
listofvalues.append(int(twovalues[0]))
listofvalues.append(int(twovalues[1]))
return listofvalues

values = '5-9, 7-10, 3-6'
values = makelist(values)
print('Values: %d-%d' %(min(values), max(values)) )

Marcus

Thank you for your help, this is a very nice program but it does not
address the issue that I have values that do not overlap, for example
'c' and 'd' do not overlap in the above example and thus I would not
want to output 3-20 but the individual positions instead. In
addition, my inputs are not ordered from smallest to largest, thus I
could have a situation where a=5-9, b=15-20, c=7-10, etc., and I would
still want an output of: a.c = 5-10, b=15-20. I apologize for the
complication.

Thank you again!

Jay

That would be a bit more complicated...you might try using tuples of
values in a list, or writing your own class for the data handling.
Unfortunately that's not something I can just sit down and code in 5
minutes, it would take some careful thought and planning.

Marcus

 

[Mark Lawrence]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

I've tried various methods, which all fail. Does anyone have an idea
how to do this?

Thank you very much!
Jay

I haven't tried but could you adapt this:-

data = [ 1, 4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
print map(itemgetter(1), g)

found here
http://www.python.org/doc/2.6.2/library/itertools.html#module-itertools

 

[Gregor Lingl]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

Suppose you have your data given as a dictionary:

data = {'a'5,9),
'b'7,10),
'c'3,6),
'd'15,20),
'e'18,23)}

Then the following not particularly elegant
but very simple and straight forward
algorithm will solve your problem:

def values(key):
return set(range(data[key][0], data[key][1]+1))

keys = list(data.keys())
result = []
while keys:
k = [keys[0]]
keys = keys[1:]
v = values(k[0])
for l in keys[:]:
if v.intersection(values(l)):
v.update(values(l))
k.append(l)
keys.remove(l)
result.append((k,v))

# print(result) ## if you like

for k, v in result:
print(".".join(sorted(k)), "%d-%d" % (min(v), max(v)))

Regards,
Gregor

 

[Mark Dickinson]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list.  For example, here would be my input:

part name   location
a                  5-9
b                  7-10
c                  3-6
d                  15-20
e                  18-23

And here is what I need for an output:
part name   location
c.a.b            3-10
d.e               15-23

I've tried various methods, which all fail.  Does anyone have an idea
how to do this?

Here's an approach that might work. Turning it into a sensible
function and parsing input/massaging output properly are left
as an exercise. Blocks that just touch (e.g. (3, 6) then (6, 9))
are amalgamated; if this isn't what you want, and they should
be treated as separate instead, then replace 'Stop' with 'Finish'
(or any other string that sorts before 'Start').


input = [
('a', (5, 9)),
('b', (7, 10)),
('c', (3, 6)),
('d', (15, 20)),
('e', (18, 23)),
]

# create sorted list of points where an interval is entered or left
transitions = []
for name, (start, stop) in input:
transitions.extend([(start, 'Start', name), (stop, 'Stop', name)])
transitions.sort()

# scan list, accumulating blocks along the way.
count = 0
for i, (pt, startend, name) in enumerate(transitions):
if startend == 'Start':
if not count:
start = pt
names = []
count += 1
names.append(name)
else:
count -= 1
if not count:
print '.'.join(names), "%s--%s" % (start, pt)



The output that I get from this under Python 2.6 is:

c.a.b 3--10
d.e 15--23

 

[DuaneKaufman]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list.  For example, here would be my input:

part name   location
a                  5-9
b                  7-10
c                  3-6
d                  15-20
e                  18-23

And here is what I need for an output:
part name   location
c.a.b            3-10
d.e               15-23

I've tried various methods, which all fail.  Does anyone have an idea
how to do this?

Thank you very much!
Jay

Hi,

You have gotten some excellent feedback (all without installing
anything extra to your Python install), but might I suggest the use of
an interval arithmetic package to aid in this?

For instance the interval module found at: http://members.cox.net/apoco/interval/
can be put to use:

Given your data above:

part name location
a 5-9
b 7-10
c 3-6

from interval import IntervalFalse

Duane

 

[Bearophile]

Jay Bird:

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

That's sometimes known as "The Set Union Problem on Intervals".
Knowing the name of a problem is sometimes half the work People
have written papers on this.

This is a O(N^2) force-brute algorithm, you can try it on your data:

data = """part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23"""

pairs = map(str.split, data.splitlines()[1:])
triples = [map(int, i.split("-")) + [name] for (name, i) in pairs]

overlap = lambda x1,y1, x2,y2: y1 >= x2 and x1 <= y2

results = []
for (x1,y1,name) in triples:
for i, res in enumerate(results):
if overlap(x1,y1, res[0],res[1]):
results.append(name)
results[0] = min(x1, res[0])
results[1] = max(y1, res[1])
break
else:
results.append([x1, y1, name])

print results
# Output: [[3, 10, 'a', 'b', 'c'], [15, 23, 'd', 'e']]

If you have have a lot of data then it will be too much slow, and you
have to use a more complex algorithm.

If your intervals are many, they are small, and they are spread in a
not too much large range of possible values, you can create an integer
array of indexes, and you can "paint" intervals on it.

Bye,
bearophile

 

[Gregor Lingl]

For instance the interval module found at: http://members.cox.net/apoco/interval/
can be put to use:

Given your data above:

from interval import Interval
False

As my proposed solution shows this approach can
be done with on board means of Python (namely
the set type). This would be quite different though,
if you had floating point boundaries of the intervals.

Regards,
Gregor

 

[Gregor Lingl]

As my proposed solution shows this approach can
be done with on board means of Python (namely
the set type). This would be quite different though,
if you had floating point boundaries of the intervals.

.... or if the intgers involved were very big :-(

 

[Bearophile]

Mark Dickinson:

# create sorted list of points where an interval is entered or left
transitions = []
for name, (start, stop) in input:
    transitions.extend([(start, 'Start', name), (stop, 'Stop', name)])
transitions.sort()

# scan list, accumulating blocks along the way.

Oh, right, that's the usual simple solution. Silly me for showing the
dumb quadratic solution

The "pixelmap" approach may be faster if you have tons of small
intervals in a not too much large range.

Bye,
bearophile

 

[Mark Dickinson]

for i, (pt, startend, name) in enumerate(transitions):

Whoops. That line should just be:

for pt, startend, name in transitions:

The enumerate was accidentally left-over from a more
complicated version.

 

[kj]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

I've tried various methods, which all fail. Does anyone have an idea
how to do this?

This problem is basically isomorphic to the problem of finding
connected components in an undirected graph. If your parts are
nodes in a graph, there's an edge between them if they overlap.

The following is probably overkill, but it works. It uses the
module pygraph, which you can download from

http://code.google.com/p/python-graph/

The real work is done by its connected_components function.


import pygraph
from pygraph.algorithms.accessibility import connected_components

class Part(object):
def __init__(self, name, start, finish):
self.name = name
if start >= finish:
raise ValueError("start must be strictly less than finish")
self.start = start
self.finish = finish
def __str__(self):
return self.name

def combine_parts(parts):
gr = pygraph.graph()
gr.add_nodes(parts)
# connect the nodes
for i in range(len(parts) - 1):
part_i = parts
for j in range(i + 1, len(parts)):
part_j = parts[j]
if (part_j.start <= part_i.finish <= part_j.finish or
part_i.start <= part_j.finish <= part_i.finish):
gr.add_edge(part_i, part_j)

cc = connected_components(gr)
c2n = {}
# build connected components as lists
for k, v in cc.items():
c2n.setdefault(v, []).append(k)

ret = []
for nodes in c2n.values():
nodes.sort(key=lambda x: x.start)
name = '.'.join(x.name for x in nodes)
start = min(x.start for x in nodes)
finish = max(x.finish for x in nodes)
ret.append((name, start, finish))

return ret

if __name__ == '__main__':
data = [Part('a', 5, 9),
Part('b', 7, 10),
Part('c', 3, 6),
Part('d', 15, 20),
Part('e', 18, 23)]
print combine_parts(data)


When you run the script above, the output is

[('c.a.b', 3, 10), ('d.e', 15, 23)]

HTH,

kynn

 

[MRAB]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

I've tried various methods, which all fail. Does anyone have an idea
how to do this?

>>> parts = [(5, 9, "a"), (7, 10, "b"), (3, 6, "c"), (15, 20, "d"), (18, 23, "e")]
>>> parts.sort()
>>> parts [(3, 6, 'c'), (5, 9, 'a'), (7, 10, 'b'), (15, 20, 'd'), (18, 23, 'e')]
>>> # Merge overlapping intervals.
>>> pos = 1
>>> while pos < len(parts):

# Merge the pair in parts[pos - 1 : pos + 1] if they overlap.
p, q = parts[pos - 1 : pos + 1]
if p[1] >= q[0]:
parts[pos - 1 : pos + 1] = [(p[0], max(p[1], q[1]),
p[2] + "." + q[2])]
else:
# They don't overlap, so try the next pair.
pos += 1

[(3, 10, 'c.a.b'), (15, 23, 'd.e')]

 

[kj]

Here's an approach that might work. Turning it into a sensible
function and parsing input/massaging output properly are left
as an exercise. Blocks that just touch (e.g. (3, 6) then (6, 9))
are amalgamated; if this isn't what you want, and they should
be treated as separate instead, then replace 'Stop' with 'Finish'
(or any other string that sorts before 'Start').

input =3D [
('a', (5, 9)),
('b', (7, 10)),
('c', (3, 6)),
('d', (15, 20)),
('e', (18, 23)),
]

# create sorted list of points where an interval is entered or left
transitions =3D []
for name, (start, stop) in input:
transitions.extend([(start, 'Start', name), (stop, 'Stop', name)])
transitions.sort()

# scan list, accumulating blocks along the way.
count =3D 0
for i, (pt, startend, name) in enumerate(transitions):
if startend =3D=3D 'Start':
if not count:
start =3D pt
names =3D []
count +=3D 1
names.append(name)
else:
count -=3D 1
if not count:
print '.'.join(names), "%s--%s" % (start, pt)

Very cool.

kynn

 

[Bearophile]

kj:

    # connect the nodes
    for i in range(len(parts) - 1):
        part_i = parts
        for j in range(i + 1, len(parts)):

Note that's O(N^2), see the O(sort) standard solution by Mark
Dickinson.

Bye,
bearophile

 

[Jay Bird]

Hi everyone,

I wanted to thank you all for your help and *excellent* discussion. I
was able to utilize and embed the script by Grigor Lingl in the 6th
post of this discussion to get my program to work very quickly (I had
to do about 20 comparisons per data bin, with over 40K bins in
total). I am involved in genomic analysis research and this problem
comes up a lot and I was surprised to not have been able to find a
clear way to solve it. I will also look through all the tips in this
thread, I have a feeling they may come in handy for future use!

Thank you again,
Jay

 

[Mensanator]

Jay Bird schrieb:

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list.  For example, here would be my input:

part name   location
a                  5-9
b                  7-10
c                  3-6
d                  15-20
e                  18-23

And here is what I need for an output:
part name   location
c.a.b            3-10
d.e               15-23

Suppose you have your data given as a dictionary:

data = {'a'5,9),
         'b'7,10),
         'c'3,6),
         'd'15,20),
         'e'18,23)}

Then the following not particularly elegant
but very simple and straight forward
algorithm will solve your problem:

def values(key):
     return set(range(data[key][0], data[key][1]+1))

keys = list(data.keys())
result = []
while keys:
     k = [keys[0]]
     keys = keys[1:]
     v = values(k[0])
     for l in keys[:]:
         if v.intersection(values(l)):
             v.update(values(l))
             k.append(l)
             keys.remove(l)
     result.append((k,v))

# print(result) ## if you like

for k, v in result:
     print(".".join(sorted(k)), "%d-%d" % (min(v), max(v)))

Regards,
Gregor

I've tried various methods, which all fail.  Does anyone have an idea
how to do this?

Thank you very much!
Jay

I was thinking sets, too.

import random

def overlap():
merge_count = 0
datam.append(data.pop(0))
while len(data)>0:
d0 = data.pop(0)
dmi = 0
dmtemp = datam[:]
while d0:
dmtest = d0[1].intersection(dmtemp[dmi][1])
#print(d0,dmtemp[dmi],dmtest)
if len(dmtest)>0: # overlap
dmtest = d0[1].union(dmtemp[dmi][1])
datam[dmi] = (d0[0]+dmtemp[dmi][0],dmtest)
d0 = None
dmi = 0
merge_count += 1
else:
dmi += 1
if dmi == len(dmtemp):
datam.append(d0)
d0 = None
return merge_count # repeat until 0 returned

## OP data
##data=[]
##data.append(('a',set([i for i in range(5,9+1)])))
##data.append(('b',set([i for i in range(7,10+1)])))
##data.append(('c',set([i for i in range(3,6+1)])))
##data.append(('d',set([i for i in range(15,20+1)])))
##data.append(('e',set([i for i in range(18,23+1)])))
##datam = []
##
##print()
##for j in data: print(j)
##print()
##
##
##overlap()
##
##for i in datam:
## print(i[0],min(i[1]),max(i[1]))
##
## ('a', {8, 9, 5, 6, 7})
## ('b', {8, 9, 10, 7})
## ('c', {3, 4, 5, 6})
## ('d', {15, 16, 17, 18, 19, 20})
## ('e', {18, 19, 20, 21, 22, 23})
##
## cba 3 10
## ed 15 23



## special case - repeat overlap test until no merges

data = [('A', {79, 80, 81, 82, 83, 84, 85, 86}),
('B', {96, 89, 90, 91, 92, 93, 94, 95}),
('C', {21, 22, 23, 24, 25, 26, 27, 28}),
('D', {64, 65, 66, 67, 68, 69, 62, 63}),
('E', {72, 73, 74, 75, 76, 77, 78, 79}),
('F', {65, 66, 67, 68, 69, 70, 71, 72}),
('G', {11, 12, 13, 14, 15, 16, 17, 18}),
('H', {24, 25, 26, 27, 28, 29, 30, 31}),
('I', {32, 33, 34, 35, 36, 37, 38, 31}),
('J', {81, 82, 83, 84, 85, 86, 87, 88})]
datam = []

## ('A', {55, 56, 57, 58, 59, 60, 61, 62})
## ('B', {64, 57, 58, 59, 60, 61, 62, 63})
## ('C', {10, 11, 12, 13, 14, 15, 16, 17})
## ('D', {32, 25, 26, 27, 28, 29, 30, 31})
## ('E', {54, 55, 56, 57, 58, 59, 60, 61})
## ('F', {64, 65, 66, 59, 60, 61, 62, 63})
## ('G', {41, 42, 43, 44, 45, 46, 47, 48})
## ('H', {67, 68, 69, 70, 71, 72, 73, 74})
## ('I', {55, 56, 57, 58, 59, 60, 61, 62})
## ('J', {64, 65, 66, 67, 68, 69, 62, 63})
##
## JIFEBA 54 69
## C 10 17
## D 25 32
## G 41 48
## H 67 74 <--- NFG overlaps JIFEBA

print()
for j in data: print(j)
print()

merges = 1 # corrects above
while merges > 0:
merges = overlap()
print(merges)
if merges>0:
data = datam[:]
datam = []

for i in datam:
print(i[0],min(i[1]),max(i[1]))

## corrected
##
## ('A', {79, 80, 81, 82, 83, 84, 85, 86})
## ('B', {96, 89, 90, 91, 92, 93, 94, 95})
## ('C', {21, 22, 23, 24, 25, 26, 27, 28})
## ('D', {64, 65, 66, 67, 68, 69, 62, 63})
## ('E', {72, 73, 74, 75, 76, 77, 78, 79})
## ('F', {65, 66, 67, 68, 69, 70, 71, 72})
## ('G', {11, 12, 13, 14, 15, 16, 17, 18})
## ('H', {24, 25, 26, 27, 28, 29, 30, 31})
## ('I', {32, 33, 34, 35, 36, 37, 38, 31})
## ('J', {81, 82, 83, 84, 85, 86, 87, 88})
##
## 5
## 1
## 0
## DJFEA 62 88
## B 89 96
## IHC 21 38
## G 11 18


# random sequences
data = []
for j in range(12):
q = random.randint(0,90)
r = q+12
data.append((chr(j+65),set([x for x in range(q,r)])))
datam = []

print()
for j in data: print(j)
print()

merges = 1 # corrects above
while merges > 0:
merges = overlap()
print(merges)
if merges>0:
data = datam[:]
datam = []

for i in datam:
print(i[0],min(i[1]),max(i[1]))

## ('A', {3, 4, 5, 6, 7, 8, 9, 10})
## ('B', {76, 77, 78, 79, 80, 81, 82, 83})
## ('C', {43, 44, 45, 46, 47, 48, 49, 50})
## ('D', {42, 43, 44, 45, 46, 47, 48, 49})
## ('E', {23, 24, 25, 26, 27, 28, 29, 30})
## ('F', {49, 50, 51, 52, 53, 54, 55, 56})
## ('G', {76, 77, 78, 79, 80, 81, 82, 83})
## ('H', {1, 2, 3, 4, 5, 6, 7, 8})
## ('I', {37, 38, 39, 40, 41, 42, 43, 44})
## ('J', {83, 84, 85, 86, 87, 88, 89, 90})
##
## 6
## 0
## HA 1 10
## JGB 76 90
## IFDC 37 56
## E 23 30

## ('A', {64, 65, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63})
## ('B', {34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45})
## ('C', {16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27})
## ('D', {70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81})
## ('E', {64, 65, 66, 67, 56, 57, 58, 59, 60, 61, 62, 63})
## ('F', {34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45})
## ('G', {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11})
## ('H', {64, 65, 66, 55, 56, 57, 58, 59, 60, 61, 62, 63})
## ('I', {44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55})
## ('J', {64, 65, 66, 67, 68, 57, 58, 59, 60, 61, 62, 63})
## ('K', {96, 97, 98, 99, 88, 89, 90, 91, 92, 93, 94, 95})
## ('L', {96, 97, 98, 99, 100, 89, 90, 91, 92, 93, 94, 95})
##
## 6
## 1
## 0
## FBJIHEA 34 68
## C 16 27
## D 70 81
## G 0 11
## LK 88 100

 

[Albert van der Horst]

Hi everyone,

I've been trying to figure out a simple algorithm on how to combine a
list of parts that have 1D locations that overlap into a non-
overlapping list. For example, here would be my input:

part name location
a 5-9
b 7-10
c 3-6
d 15-20
e 18-23

And here is what I need for an output:
part name location
c.a.b 3-10
d.e 15-23

I've tried various methods, which all fail. Does anyone have an idea
how to do this?

That is an algorithmic question and has little to do with Python.
You could proceed as follows:
- Order your data by the lower limit
- Combine everything with the same lower limit.
- Then combine every pair of consecutive entries that overlap.

(In you case the second step is not needed.)