Overlap in python
bearophileHUGS at lycos.com
Tue Aug 4 23:00:37 CEST 2009
> # 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)])
> # 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.
More information about the Python-list