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] -- http://mail.python.org/mailman/listinfo/python-list