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

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)

A Haskell version.

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

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

MUMPS language

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

6

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

Here’s a solution in C.

Output:

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

Here’s a Python answer in a functional style:

Thanks, Mike!

Klong language

[1 2 3 6 7 8]

6

“end”

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

15

“end”

Klong language – Commented version

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”