## 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

Pages: 1 2

### 5 Responses to “Free Time”

1. Francesco said

```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 sally
```

not happy with the compress function though…

2. Paul said

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 if a else HI
begin = lambda a: a 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))

ov = [b for b in all_busy if overlap(b, busy)]
new = union(busy, *ov)
all_busy -= set(ov)

def union_all_busy(busy):
all_busy = set()
for b in 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)]
"""

```
3. matthew said

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)
```
4. Paul said

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]))
_, stop = busy.pop()
while busy and busy[-1] <= stop: # overlap
stop = max(stop, busy.pop())   # 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)]
```