Free Time

December 5, 2014

We’ll represent time as integers, which you could take to be hours, or quarter-hour setments, or even minutes. Thus, a person’s busy-time intervals are represented as a list of pairs of integers, each pair in ascending order and each start-time after the previous end-time. You may assume the lists are ordered and there are no overlaps. Thus:

(define mike '((1 5) (10 14) (19 20) (21 24) (27 30)))
(define sally '((3 5) (12 15) (18 21) (23 24)))

Our algorithm makes a boolean array filled with #t values starting from the lowest time reference and ending at the highest time reference, representing free time. Then we iterate over each interval for each person, marking all busy times as #f. Finally we scan the array and report any times that remain #t. It is easy to generalize the problem to more than two people.

(define (free-time . xss)
  (let* ((lo (apply min (flatten xss)))
         (hi (apply max (flatten xss)))
         (len (- hi lo -1))
         (free (make-vector len #t)))
    (do ((xss xss (cdr xss))) ((null? xss))
      (do ((xs (car xss) (cdr xs))) ((null? xs))
        (do ((i (caar xs) (+ i 1))) ((< (cadar xs) i))
          (vector-set! free (- i lo) #f))))
    (let loop ((in-free? #f) (start #f) (i 0) (xs (list)))
      (cond ((and in-free? (= i len))
              (reverse (cons (list start (+ i lo)) xs)))
            ((= i len)
              (reverse xs))
            ((and in-free? (vector-ref free i))
              (loop #t start (+ i 1) xs))
            ((and in-free? (not (vector-ref free i)))
              (loop #f #f (+ i 1) (cons (list start (+ i lo -1)) xs)))
            ((vector-ref free i)
              (loop #t (+ i lo) (+ i 1) xs))
            ((not (vector-ref free i))
              (loop #f #f (+ i 1) xs))))))

The nested do loops process each person, each busy-time interval, and each time reference, setting each of those times #f. Then the named-let loop runs through the vector. There are two stopping conditions, depending on whether or not there is a free-time interval currently open, and there are four continuing conditions, depending on whether or not there is a free-time interval currently open and whether or not the current time is free. Here’s a sample run:

> (free-time mike sally)
((6 9) (16 17) (25 26))

We used flatten from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/AVyPF6oO.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: