I'm learning for the exam from algorithms and data structures (that I have in a month) and I can't manage with finding efficient algorithm for this problem:
We are given $1\le n\le 5000$ points on the line. Each point has different natural coordinate $0\le d \le 10^6$ and (not necessarily different) natural point-time $0\le t \le 10^9$ in seconds. We can start at any point and in each second change our current coordinate by +/-$1$. The problem is to visit all the points in such order that every point is visited before elapsing his point-time. Find the minimum total time (in seconds) of this trip, or say it's impossible.
For example, $5$ points given (coordinate, point-time):
$(1,3), \ (3,1), \ (5,6), \ (8,19), \ (10,15)$, it's possible, when we take a trip visiting coordinates: $3\rightarrow 1\rightarrow 5 \rightarrow 8 \rightarrow 10$, we got minimum total time, which is equal to: $11$.
My first idea was to sort all the points lexicographically by: (point-time, coordinate), and then visit them in this order. Of course, when there are points between $i$-th point and $(i+1)$-th point, we can visit them before visiting $(i+1)$-th point. But unfortunately, there is no argument why such greedy approach should work, despite the fact that it would be difficult to implement. Maybe I'm trying to solve it too quickly? $n$ is small so, $O(n^2)$ should be ok, I suppose.
I found other examples of the input, thinking maybe it will help me finding the solution. But now I only see that I have to find one permutation of all possible $n!$ permutations.
points (also given by coordinate, point time respectively): $(0,4), \ (1,2), \ (4,5)$ -> surprisingly (I think) we have to visit them: $0\rightarrow 1 \rightarrow 4$, because any different order does not satisfy condition in one before last sentence in problem text.
points: $(0,7), \ (1,2), \ (2,1), \ (3, 4), \ (4,11)$, the only funny way is: $2\rightarrow 1\rightarrow 3\rightarrow 0\rightarrow 4$, which takes us $10$ seconds.
Can anyone help?