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

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):

print list(on_times)

2. Globules said

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

---

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

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"
:""
[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

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