## Television Time

### March 20, 2018

I like this problem because it’s a good way to show off the Standard Prelude; the problem is easy to solve because all the hard work has already been done:

```(define (tv-time xs)
(length (unique = (sort <
(mappend (lambda (x) (range (car x) (cadr x))) xs)))))```

`Range` builds a list of times at which the television is on during a single interval, then `mappend` (which is like `map` but builds the output list using `append` instead of `cons`) builds a list of all the times the television is on during all the intervals, with some times repeated. `Sort` brings like times together, `unique` discards duplicate times, and `length` counts the times. Here are some examples:

```> (tv-time '((1 4) (2 3))) ; 1, 2, 3
3
> (tv-time '((4 6) (1 2))) ; 1, 4, 5
3
> (tv-time '((1 4) (6 8) (2 4) (7 9) (10 15))) ; 1, 2, 3, 6, 7, 8, 10, 11, 12, 13, 14
11```

You can run the program at https://ideone.com/P1q7Vv.

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.start;
uint_t end = intervals.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