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.

###### Answered By : lkese3ker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66268

3200 people like this