Overlap in python

Marcus Wanner marcusw at cox.net
Wed Aug 5 13:13:23 CEST 2009


On 8/4/2009 6:09 PM, MRAB wrote:
>  >>> 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')]
> 
That's the best solution I've seen so far. It even has input/output 
formatted as close as is reasonably possible to the format specified.

As we would say in googlecode, +1.

Marcus




More information about the Python-list mailing list