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

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “Free Time”

  1. Francesco said
    December 5, 2014 at 9:14 PM

    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…

  3. Paul said
    December 6, 2014 at 4:50 PM

    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)]
"""
  4. matthew said
    December 7, 2014 at 3:36 PM

    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)
  5. Paul said
    December 8, 2014 at 10:29 AM

    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 comment