Merging overlapping spans/ranges

[Jordan Rastrick]

Should work fine as far as I can see. Of course, thats not very
'pythonic' - I should probably give at least 10 different unit tests
that it passes ;)

Its gratifying to know I'm not the only one who needed that final
yield.

Jim Sizelove wrote:
> Bengt Richter wrote:
> > 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 ;-)
>
> It is with some trepidation that I write this message; after hanging
> around in c.l.p for the better part of a year, I have come to expect
> Bengt's messages to be right-on and error-free.
>
> However this time...  :)
> >  >>> 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)]
>
> There can be a problem in mergespans if one span fits inside another:
>
>   >>> spans = [(0,5), (4,7), (2,3), (9,14), (12,17)]
>   >>> list(mergespans(spans))
>   [(0, 3), (4, 7), (9, 17)]
>
> Here is a revised version (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:
>   ...             if end < e:
>   ...                 end = e
>   ...             continue
>   ...         yield start, end
>   ...         start,end = s,e
>   ...     if start is not None:
>   ...         yield start, end
>   ...
>   >>> list(mergespans([(0,5), (4,7), (2,3), (9,14), (12,17)]))
>   [(0, 7), (9, 17)]
>   >>> list(mergespans([(0,3), (4,7), (2,5), (9,14), (12,17)]))
>   [(0, 7), (9, 17)]
>
> Can anyone find any other errors in this? ;-)
> 
> With humble regards,
> Jim Sizelove