Merging overlapping spans/ranges

Bengt Richter bokr at oz.net
Tue May 10 19:52:44 EDT 2005


On Tue, 10 May 2005 15:14:47 +0200, Max M <maxm at mxm.dk> wrote:

>I am writing a "find-free-time" function for a calendar. There are a lot 
>of time spans with start end times, some overlapping, some not.
>
>To find the free time spans, I first need to convert the events into a 
>list of non overlapping time spans "meta-spans".
>
>This nice ascii graph should show what I mean.
>
>1) ---
>2)     ---
>3)   ---
>4)          -----
>5)             -----
>
> >> -------  -------- # meta spans
>
>I can then iterate through the meta-spans and find non-busy times.
>
>I have written the class below, but it is rather O^2, so I wondered if 
>anybody has an idea for a better approach?
>
>

 >>> spans = [(0,3), (4,7), (2,5), (9,14), (12,17)]
 
Non-recommended one-liner:

 >>> reduce(lambda L,se: (L and se[0]<=L[-1][1] and (L.append((L.pop()[0], se[1])) or L)) or L.append(se) or L ,sorted(spans), [])
 [(0, 7), (9, 17)]

Regards,
Bengt Richter



More information about the Python-list mailing list