Overlap in python

Bearophile bearophileHUGS at lycos.com
Tue Aug 4 23:00:37 CEST 2009

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.


More information about the Python-list mailing list