On Tue, 10 May 2005 15:14:47 +0200, Max M <[EMAIL PROTECTED]> 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 ;-)
>>> 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)] Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
