World's most popular travel blog for travel bloggers.

# Maximum waiting time between events such that k events are not missed

, ,
Problem Detail:

I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:

In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.

• Lap times last exactly a minute, and they are booked for the full minute.
• If we use a free lap time slot, we must wait x seconds until we can use another.

We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.

Example:

With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.

So I tried hard and came up with this recurrence: $$X[i,m] = \max_{1 \leq j \leq i}\ (\min\ (X[j,m-1],\sum_{k=j}^{n-1}abs(s_{k+1} - s_k)))$$ Where X[i,m] means "the maximum distance that I can pick in the subset $\{s_1,s_2,...,s_i\}$ so that I lap at least m times".

Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested).

Any ideas or hints?

Thank you.

The solution was using a binary search on the time between laps and since every checking of the value is linear time, computing the solution is cheap. Thank you anyway.