Merging overlapping spans/ranges
Bengt Richter
bokr at oz.net
Tue May 10 19:07:51 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?
>
Maybe (not tested beyond what you see ;-)
>>> def mergespans(spans):
... start = end = None
... for s,e in sorted(spans):
... if start is None: start, end = s,e; continue
... if s <= end: end = e; continue
... yield start, end
... start,end = s,e
... if start is not None: yield start, end
...
>>> spans = [(0,3), (4,7), (2,5), (9,14), (12,17)]
>>> list(mergespans(spans))
[(0, 7), (9, 17)]
Regards,
Bengt Richter
More information about the Python-list
mailing list