Here's an interesting question I came upon:
Let's just say on a number line of length
0 < M <= 1,000,000,000, you given
1 < N <= 100,000) integer pairs of points. In each pair, the first point represents where an object is currently located, and the second point represents where an object should be moved. (Keep in mind the
second point may be smaller than the
Now, assume you start at the point
0 and have a cart that can hold
1 object. You want to move all objects from their initial positions to their respective final positions while traveling the least distance along the number line (not displacement). You have to end up on point
Now, I've been trying to reduce this problem to a simpler problem. To be honest I can't even think of a brute force (possibly greedy) solution. However, my first thought was to degenerate a backwards movement to two forward movements, but that doesn't seem to work in all cases.
I drew out these
3 sample test cases in here:
The answer to the first testcase is
12. First, you pick up the
red item at point
0. Then you move to point
6 (distance =
6), drop the
red item temporarily, then pick up the
green item. Then you move to point
5 (distance =
1) and drop the
green item. Then you move back to point
6 (distance =
1) and pick up the
red item you dropped, move to point 9 (distance =
3), then move to point
10 (distance =
1) to finish off the sequence.
The total distance traveled was
6 + 1 + 1 + 3 + 1 = 12, which is the minimum possible distance.
The other two cases have answers of
12, I believe. However, I can't find a general rule to solve it.
Anyone got any ideas?