Television Time

March 20, 2018

Today’s exercise is an interview question:

There is a room with a television and people come in and out of the room to watch it; the television is on only when there is at least one person in the room. For each person that enters the room, we record the start and end time, represented as a two-element array containing the starting time (inclusive) and ending time (exclusive), with times as integers (you can think of hours, or minutes, or any interval you like). We want to know how long the television is on. For instance, given the list of intervals (1 4), (6 8), (2 4), (7 9), the television is on at times 1, 2, 3 from the first interval, times 6 and 7 from the second interval, times 2 and 3 from the third interval, and times 7 and 8 from the first interval, a total of 6 times the television is on (at times 1, 2, 3, 6, 7 and 8).

Your task is to write a program that takes a list of intervals and returns the number of times at which the television is on. 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.

Advertisements

Pages: 1 2

10 Responses to “Television Time”

  1. Mithran said

    intervals_list = [(1, 4), (6, 8), (2, 4), (7, 9)]
    on_times = set()

    for start, end in intervals_list:
    for time in range(start, end):
    on_times.add(time)

    print list(on_times)

  2. Globules said

    A Haskell version.

    import Data.List.Ordered (nubSort)
    
    timesOn :: (Enum a, Ord a) => [(a, a)] -> [a]
    timesOn = nubSort . concatMap (\(s, e) -> [s .. pred e])
    
    main :: IO ()
    main = do
      print $ timesOn [(1, 4), (6, 8), (2, 4), (7, 9)]
      print $ timesOn [(1, 4)]
      print $ timesOn ([] :: [(Int, Int)])
      -- Works with non-integers, too.
      print $ timesOn [('c', 'f'), ('j', 'm'), ('d', 'h')]
    
    $ ./teletime
    [1,2,3,6,7,8]
    [1,2,3]
    []
    "cdefgjkl"
    
  3. chaw said

    Here is a solution in standard Scheme. with time- and
    space-complexity linear in the size of the input. (I believe the
    other solutions, so far, require space and time that are exponential
    in the size of the input.)

    (import (scheme base)
            (scheme write)
            (only (srfi 95) sort)
            (only (srfi 8) receive))
    
    (define (intervals-cover-length intervals)
      (let f ((intervals (sort intervals < car))
              (marker -inf.0)
              (len 0))
        (if (null? intervals)
            len
            (receive (start stop) (apply values (car intervals))
              (let ((marker (max marker start)))
                (f (cdr intervals)
                   (max marker stop)
                   (+ len (max 0 (- stop marker)))))))))
    
    (display (intervals-cover-length '((1 4) (6 8) (2 4) (7 9))))
    (display (intervals-cover-length '((0 1e9))))
    (newline)
    

  4. Globules said

    Here’s an alternate version in Haskell, which (like chaw’s) just prints the total time spanned by the intervals.

    import Data.List (sort)
    import Data.Ratio ((%))
    
    -- Collapse the sorted argument into the equivalent list of disjoint intervals.
    -- We assume that the start value of each interval is less than the end value.
    collapse :: Ord a => [(a, a)] -> [(a, a)]
    collapse (i1@(s1, e1) : i2@(s2, e2) : is)
      | e1 >= s2  = collapse ((s1, max e1 e2) : is)
      | otherwise = i1 : collapse (i2 : is)
    collapse is = is
    
    -- The total length of "time" covered by the intervals.  We ignore intervals in
    -- which the start time is greater than the end time.
    timeOn :: (Num a, Ord a) => [(a, a)] -> a
    timeOn = sum . map (uncurry subtract) . collapse . sort . filter (uncurry (<))
    
    main :: IO ()
    main = do
      print $ timeOn [(1, 4), (6, 8), (2, 4), (7, 9)]
      print $ timeOn [(2, 2), (1, 4)]
      print $ timeOn [(3, 2)]
      print $ timeOn [(0, 1e9)]
    
      -- Works with rationals, too.
      print $ timeOn [(5 % 8, 11 % 8), (2 % 1, 5 % 2), (1 % 8, 7 % 8)]
    
    $ ./teletime2
    6
    3
    0
    1.0e9
    7 % 4
    
  5. Steve said

    MUMPS language

    XJSG     ;
             Q
             ;
    TIMES(STR) ;
             ; DECLARE VARIABLES
             N I,J,MAX,MIN,SEG,TIMES
             ; INITIALIZE COUNTER
             S TIMES=0
             ; LOOP THROUGH SEGMENTS
             F I=1:1:$L(STR,",") D
             . ; FOR EACH SEGMENT, GET MIN AND MAX
             . S SEG=$P(STR,",",I),MIN=$P(SEG," "),MAX=$P(SEG," ",2)
             . ; FOR EACH NUMBER THROUGH MIN AND MAX-1
             . ;   IF NUMBER NOT ALREADY ACCUMULATED, ACCUMULATE IT
             . ;      AND INCREMENT COUNT OF TIMES
             . F J=MIN:1:MAX-1 S:'$D(TIMES(J)) TIMES=TIMES+1,TIMES(J)=""
             Q TIMES
    
    ---
     
    Without comments:
    XJSG     ;
             Q
             ;
    TIMES(STR) ;
             N I,J,MAX,MIN,SEG,TIMES
             S TIMES=0
             F I=1:1:$L(STR,",") D
             . S SEG=$P(STR,",",I),MIN=$P(SEG," "),MAX=$P(SEG," ",2)
             . F J=MIN:1:MAX-1 S:'$D(TIMES(J)) TIMES=TIMES+1,TIMES(J)=""
             Q TIMES
    

    LAB>W $$TIMES^XJSG(“1 4,6 8,2 4,7 9”)
    6

  6. Steve said

    @Mithran: I always like to see short solutions. Language?

  7. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef unsigned int uint_t;
    
    typedef struct {
      uint_t start;
      uint_t end;
    } interval_t;
    
    static int compar(const void* a, const void* b) {
      uint_t a_start = ((interval_t*)a)->start;
      uint_t b_start = ((interval_t*)b)->start;
      if (a_start > b_start) {
        return 1;
      } else if (a_start < b_start) {
        return -1;
      } else {
        return 0;
      }
    }
    
    // destructive: sorts intervals
    uint_t calc_television_time(
        interval_t* intervals, size_t n) {
      if (n == 0) return 0;
      qsort(intervals, n, sizeof(interval_t), compar);
      uint_t television_time = 0;
      uint_t start = intervals[0].start;
      uint_t end = intervals[0].end;
      for (size_t i = 1; i < n; ++i) {
        if (intervals[i].start > end) {
          television_time += end - start;
          start = intervals[i].start;
        }
        if (intervals[i].end > end) {
          end = intervals[i].end;
        }
      }
      television_time += end - start;
      return television_time;
    }
    
    int main(void) {
      interval_t intervals[] = {
        {1, 4},
        {6, 8},
        {2, 4},
        {7, 9}
      };
      size_t n = sizeof(intervals) / sizeof(interval_t);
      uint_t television_time = calc_television_time(intervals, n);
      printf("%u\n", television_time);
      return EXIT_SUCCESS;
    }
    

    Output:

    6
    
  8. Mike said

    @steve, Mithran’s answer looks like Python that had the leading whitespace eaten.

    Here’s a Python answer in a functional style:

    import itertools as it
    
    def on_times(intervals):
        return len(set().union(*it.starmap(range,intervals)))
    
  9. Steve said

    Thanks, Mike!

    Klong language

    fh2::{?(z,(x+!(y-x)))}
    fh::{[l t]; l::[]; t::x; {l::fh2(x@0; x@1; l)}'t; l::{#(l@x)}'<l; .p(l); .p(#l); "end"}
    
        fh([[6 8] [1 4] [2 4] [7 9]])
    

    [1 2 3 6 7 8]
    6
    “end”

        fh([[6 8] [1 4] [2 4] [7 9] [11 20]])
    

    [1 2 3 6 7 8 11 12 13 14 15 16 17 18 19]
    15
    “end”

  10. Steve said

    Klong language – Commented version

    
    steve@steve-VirtualBox:~/klong$ cat tv-time.kg 
    :" Televsion Time - Programming Praxis"
    :""
    .comment("end-of-comments")
    [l] -       Declare a local variable
    l::[] -     Assign empty list to l
    ? -        Input list, output unique elements of list
    l1,l2 -   Concatenate 2 lists
    x@n -  Return nth element of list (0-based)
    !n -      Return list of integers form 0 to n-1
    {...} -    Definition of function
    {...}'n - Execute function for every element of list n
    #l -       Return length of list
    <l -       Return list where each element is the sorted position 
               of original list.  So if l = [2 1 3] then <l = [1 0 2],
               because l@1 is 1, l@0 is 2 and l@2 is 3.
    .p(x) -  Print x
    end-of-comments
    
    fh::{[l]; l::[]; {l::?(l,((x@0)+!((x@1)-(x@0))))}'x; l::{#(l@x)}'<l; .p(l); .p(#l); "end"}
    
    

    steve@steve-VirtualBox:~/klong$ ./kg
    Klong 20180213
    ]l tv-time.kg
    loading “./tv-time.kg”
    fh([[1 4] [6 8] [2 4] [7 9]])
    [1 2 3 6 7 8]
    6
    “end”
    fh([[1 4] [10 15] [6 8] [2 4] [7 9]])
    [1 2 3 6 7 8 10 11 12 13 14]
    11
    “end”

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: