Overlap in python

[MRAB]

Jay Bird wrote:
> 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


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