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.

Pages: 1 2

5 Responses to “Free Time”

  1. Francesco said

    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 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[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)]
    """
        
    
  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][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)]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: