Merging overlapping spans/ranges

[Jim Sizelove]

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