Online computation of coverage time for a time range

Question

Suppose I have a time range, it could be represented by a video as the time when it starts(0 s) and the time it ended. For instance, with a video that lasts 1 min I have a time range that goes from 0s to 60s.

Suppose I have an online stream that sends me time intervals like this:

[0, 10]
[8, 14]
[2, 3]
[20, 25]

Suppose that these intervals represents time passed playing a video. I would like to compute, each time a new interval arrives, the effective time the video was played without repetition.

It should be something like this:

[0, 10]
#time_played = 10s
[8, 14]
#time_played = 14s because [0,10]+[8,14] -> [0,14] is the effective time interval
[2, 3]
#time_played = 14s because this time interval has already been covered
[20, 25]
#time_played = 19s because [0, 14] + [20, 25] makes 19s the video was effectively played

I cannot find a solution because I don't event know what is the problem definition. What do you think could be a clever way to solve this problem using python

score 1 · Answer 1 · answered Oct 31 '19 at 11:14

You could append all the times that have passed to an array, then get the length of the array like so.

times = []
def get_time(interval = None): # If we don't pass the interval it will return the current time passed
    if interval:
        for time in range(interval[0], interval[1]):
            if time not in times: # Don't append to the array if we already have the time value
                times.append(time)
    return len(times) # Return the length of the array of times


print(get_time([0, 10]))
#time_played = 10s
print(get_time([8, 14]))
#time_played = 14s because [0,10]+[8,14] -> [0,14] is the effective time interval
print(get_time([2, 3]))
#time_played = 14s because this time interval has already been covered
print(get_time([20, 25]))
#time_played = 19s because [0, 14] + [20, 25] makes 19s the video was effectively played

## Expected output:
## 10
## 14
## 14
## 19

Hope this is helpful

Thank you, this solution solves the problem. Nonetheless, it needs to be admitted that this solution is memory-consuming because you need to store all the time instants, while I think you could store only the extrems. Upvoted, but I am waiting for some stunning, hyper-clever solution :D — BalrogOfMoria, Oct 31 '19 at 11:20
I have posted a new answer which I think should sort the memory issue. I have posted it as new rather than editing this one due to the fact that this one may be simpler for a beginner to understand, so if a someone has a similar question they can better understand how this works — Minion3665, Oct 31 '19 at 17:05

score 0 · Answer 2 · answered Oct 31 '19 at 17:03

Here's my new answer. The get time function does a few things: 1, calculating the time- The functon creates a local list called times and appends the time values to it (as in the previous answer, but this time we use a local list so it isn't as memory consuming), factoring in all the previous_intervals and the intervals passed to the function. It then saves the time played to a variable called time_played. This is what will be returned later. 2, calculating the previous_intervals- The previous_intervals variable is cleared then, if the number of times are greater than 0 (to avoid pop(0) raising an IndexError, if not then the previous_intervals are empty anyway) the program will sort the times and find out all the intervals needed to create the list of times that are there. It will then save to previous_intervals for next time the function is run 3, returning- the program returns the time_played variable we created earlier. It doesn't return len(times) as since we popped out an item this will be wrong in most circumstances; it won't, however, be wrong if no seconds have passed (i.e. the interval passed was [0, 0]) so we can't return len(times) + 1 either.

Special thanks to Diarmuid O'Briain who's answer to Pairs from single list helped me to write the previous_intervals calculation

previous_intervals = []
def get_time(*intervals):
    global previous_intervals
    times = []
    intervals = list(intervals) + previous_intervals
    for interval in intervals:
        for time in range(interval[0], interval[1]):
            if time not in times:
                times.append(time)

    time_played = len(times)

    previous_intervals = []
    if len(times) > 0:
        times.sort()
        lastTime = times.pop(0)
        important_intervals = [lastTime]
        for time in times:
            if time != lastTime + 1:
                important_intervals.append(lastTime + 1)
                important_intervals.append(time)
            lastTime = time
        important_intervals.append(lastTime + 1)
        while(important_intervals):
            start_time = important_intervals.pop(0)
            end_time = important_intervals.pop(0)
            previous_intervals.append([start_time,end_time])


    return time_played

print(get_time([0, 0]))
#time_played = 0s, not 1s as would happen if we returned len(times) with correction for the missing values
print(get_time([0, 0], [1, 1]))
#time_played = 0s, we can now pass multiple intervals. ([0, 0] = No time passed + [1, 1] = No time passed, so even though this may look odd it's totally correct)
print(get_time([0, 10]))
#time_played = 10s
print(get_time([8, 14]))
#time_played = 14s because [0,10]+[8,14] -> [0,14] is the effective time interval
print(get_time([2, 3]))
#time_played = 14s because this time interval has already been covered
print(get_time([20, 25]))
#time_played = 19s because [0, 14] + [20, 25] makes 19s the video was effectively played

## Expected output:
## 0
## 0
## 10
## 14
## 14
## 19

Hope this is helpful

Online computation of coverage time for a time range

2 Answers2