# Algorithm to collect items before they expire

I thought about the following problem:

There are goods $\mathbb{G} = (g_1, \dots, g_k)$ on the line. Coordinates are expressed in meters and sorted in increasing order. All goods have different storage life $\mathbb{S} = (s_1, \dots, s_k)$ expressed in seconds. Restrictions on the data: $k < 1000, |g_i| < 10^7, |s_i| < 10^7$.

We have a bicycle, which can start from every point on the line. Bicycle's speed: 1 meter per second. The bicycle should reach all goods before their expiration and do it in minimum possible time. The problem is to create an appropriate schedule for the bicycle or tell that it's impossible.

So that I need algorithm working in $O(n^2)$ or $O(n^2\log(n))$ time.

Examples:

1. $\mathbb{G} = (1, 3, 10), \mathbb{S} = (2, 1, 100)$. We should catch the second object, then move to the left and then to the right. Answer: $(2,1,3)$.

2. $\mathbb{G} = (1, 3, 10), \mathbb{S} = (2, 1, 1)$. No optimal schedule exists as we don't have enough time to travel between 5 and 100 coordinates.

My thoughts. I was trying to use dynamic programming. I noticed that for every optimal schedule its last point is the most left or most right object on the line. Then I defined function $f[j,0]$ to be minimum possible time to catch all goods between the first and $j$-th objects so that $j$-th object is the last on the path. And $f[j,1]$ to be the same as $f[j,0]$ but last object is the leftmost.

How can we count $f[j+1, 0]$? We can try to start in $(j+1)$-th point and monotonically move to the left. Another way could be to start travelling from the point between $1$ and $j$ and end the travelling on this segment in $1$ or in $j$th point. For every such path we need to check its possibility: we need to catch objects before their expiration. So depending of what paths are possible the expression for $f[j, 0]$ could be something like: $$f[j+1, 0] = \min(f[j, 0] + g_{j+1} - g_j,\ f[j, 1]+g_j-g_1,\ g_j-g_1)\,.$$

But calculation $f[j+1, 1]$ by its previous values is not that simple.

• I don't understand the setup. You mention that the bicycle can't travel more than 1km per day. Does that equate to a speed limit of $1000/\,\mathrm{ms}^{-1}$ or is it just a maximum distance that can be travelled? If the latter, how fast can the bicycle travel? If there's no speed limit, you can just cycle from left to right at the speed of light. – David Richerby Oct 21 '15 at 9:05
• @DavidRicherby, sorry, I corrected the statement. The speed is 1 meter per second, of course – Macaronnos Oct 21 '15 at 9:09
• OK but then your first example can't be solved because the bicycle can't visit both position 5 to position 1 in the two seconds before the first item expires. Also, where does the bicycle start? Are you allowed to pick any start position? – David Richerby Oct 21 '15 at 9:11
• @DavidRicherby, it's mentioned in the statement: "We have a bicycle, which can start from every point on the line." – Macaronnos Oct 21 '15 at 9:15
• Duh, sorry. But the second example is still impossible. – David Richerby Oct 21 '15 at 9:18