Merging overlapping spans/ranges

[Mike Rovner]

Max M 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".
> 

"Almost" linear method (includes .sort() which is afaik N*logN):
[Set all priority to 1, or you will get changes in priorities as well.]

def merge(p):
     """ p is a seq of (start, priority, end)
     returns list of merged events:
       (start1, pri), (end1, 0), (start2, pri), (end2, 0), ...
     """
     all=[] # list of x, h, up, id
     for id,(l,h,r) in enumerate(p):
         all.append((l,h,1,id))
         all.append((r,h,0,id))
     all.sort()

     sl = [] # skyline solution
     slx = slh = 0 # current values
     vis = {} # active {id:h}
     for x,h,up,id in all:
         if up:
             vis[id]=h
             if h>slh:
                 sl.append((x,h))
                 slh=h
         else:
             del vis[id]
             assert h<=slh
             if h==slh:
                 v = vis.values()
                 if v:
                     h = max(v)
                 else:
                     h = 0
                 sl.append((x,h))
                 slh=h
         slx=x
     # merge same time events
     s=dict(sl)
     sl=s.keys()
     sl.sort()
     return [(k,s[k]) for k in sl]