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