Free Time
December 5, 2014
We have a very practical task today: Given the set of busy-time intervals of two people, as in a calendar, find the free-time intervals of both people so they can arrange a meeting.
Your task is to write a program to find free time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the
comments below.
Programming Praxis 
Haskell
mike = [(1,5),(10,14),(19,20),(21,24),(27,30)] sally = [(3,5),(12,15),(18,21),(23,24)] expand xs = concatMap (\\(b,e) -> [b..e]) xs compress 0 cs = compress (head cs) cs compress n (s:[]) = (n,s) : [] compress n (i:s:is) | i+1 == s = compress n (s:is) | otherwise = (n,i) : compress s (s:is) free a b = filter (not . (`elem` busy)) [1..maximum busy] where busy = expand a ++ expand b main = print $ free mike sallynot happy with the compress function though…
And the codepad link http://codepad.org/zBALWlN7
In Python. I followed a slightly different approach. I use time intervals (t1,t2) where t2 is the precise end time, so (8,10) means it start at 8 and end it 10, so possible free time start at 10.
from collections import namedtuple from itertools import chain MININF = float("-inf") INF = float("inf") mike = ((1, 6), (10, 15), (19, 21), (21, 25), (27, 31)) sally = ((3, 6), (12, 16), (18, 22), (23, 25)) john = ((5,11),) end = lambda a: a[1] if a else HI begin = lambda a: a[0] if a else HI overlap = lambda a, b: begin(a) <= end(b) and begin(b) <= end(a) def union(*a): """union of overlapping intervals""" x, y = zip(*a) return (min(x), max(y)) def add_busy(busy, all_busy): ov = [b for b in all_busy if overlap(b, busy)] new = union(busy, *ov) all_busy -= set(ov) all_busy.add(new) def union_all_busy(busy): all_busy = set() for b in busy: add_busy(b, all_busy) return sorted(all_busy) def free(busy): all_busy = [(MININF, MININF)] + union_all_busy(busy) + [(INF, INF)] return [(a2, b1) for (a1, a2), (b1, b2) in zip(all_busy, all_busy[1:])] print free(chain(sally, mike, john)) """ -> [(-inf, 1), (16, 18), (25, 27), (31, inf)] """Like Paul, I’m interpreting an interval (t1,t2) as meaning from t1 to t2. If the input sets of intervals are in order and non-overlapping, we can just merge them together, as in this Haskell function (extracting the free intervals from the merged busy intervals is straightforward):
merge [] t = t merge s [] = s merge ((x,y):s) ((z,w):t) = if y < z then (x,y):merge s ((z,w):t) else if w < x then (z,w):merge ((x,y):s) t else if w < y then merge((min x z,y):s) t else merge s ((min x z,w):t) mike = [(1,5),(10,14),(19,20),(21,24),(27,30)] sally = [(3,5),(12,15),(18,21),(23,24)] main = print (merge mike sally)In Python. First sort all busy intervals and then scan them. Any interval with start time earlier then the stop time is overlapping and the stop time is updated.
from itertools import chain def free(*busy): busy = sorted(chain(*busy), reverse=True) free_time = [] stop = float("-inf") while busy: free_time.append((stop, busy[-1][0])) _, stop = busy.pop() while busy and busy[-1][0] <= stop: # overlap stop = max(stop, busy.pop()[1]) # update stop time return free_time + [(stop, float("inf"))] mike = ((1, 6), (10, 15), (19, 21), (21, 25), (27, 31)) sally = ((3, 6), (12, 16), (18, 22), (23, 25)) john = ((5,11), (12, 15), (17, 26)) print free(sally, mike, john) # -> [(-inf, 1), (16, 17), (26, 27), (31, inf)]