Bengt Richter wrote: > 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 ;-)
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 -- http://mail.python.org/mailman/listinfo/python-list
