Merging overlapping spans/ranges

[Max M]

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?


######################################
# -*- coding: latin-1 -*-

"""
1) ---
2)     ---
3)   ---
4)          -----
5)             -----

 >> -------  --------
"""

class MetaSpans:

     """
     Populate with a list of span tuples [(start,end)], and it will make 
"meta"
     spans, with overlapping spans folded into one span.
     """

     def __init__(self):
         self.spans = []

     def add(self, span):
         start, end = span
         overlapping = [span]
         non_overlapping = []
         for spn in self.spans:
             spn_start, spn_end = spn
             # span rules for iterated spans
             starts_before = spn_start <= start
             ends_after = spn_end >= end
             is_outside = starts_before and ends_after
             starts_inside = start <= spn_start <= end
             ends_inside =  start <= spn_end <= end
             overlaps = starts_inside or ends_inside or is_outside
             if overlaps:
                 overlapping.append(spn)
             else:
                 non_overlapping.append(spn)
         # overlapping spans are changed to one span
         starts = []
         ends = []
         for start, end in overlapping:
             starts.append(start)
             ends.append(end)
         min_start = min(starts)
         max_end = max(ends)
         non_overlapping.append( (min_start, max_end) )
         self.spans = non_overlapping


     def findFreeTime(self, duration):
         self.spans.sort()




if __name__ == '__main__':

     ms = MetaSpans()
     ms.add((0,3))
     ms.add((4,7))
     ms.add((2,5))
     ms.add((9,14))
     ms.add((12,17))
     print ms.spans


     from datetime import datetime
     ms = MetaSpans()
     ms.add((datetime(2005, 1, 1, 0, 0, 0), datetime(2005, 1, 1, 3, 0, 0)))
     ms.add((datetime(2005, 1, 1, 4, 0, 0), datetime(2005, 1, 1, 7, 0, 0)))
     ms.add((datetime(2005, 1, 1, 2, 0, 0), datetime(2005, 1, 1, 5, 0, 0)))
     ms.add((datetime(2005, 1, 1, 9, 0, 0), datetime(2005, 1, 1, 14, 0, 0)))
     ms.add((datetime(2005, 1, 1, 12, 0, 0), datetime(2005, 1, 1, 17, 0, 
0)))
     print ms.spans





-- 

hilsen/regards Max M, Denmark

http://www.mxm.dk/
IT's Mad Science