Return to Question

Here's an interesting question I came upon:

Let's just say on a number line of length M, where 0 < M <= 1,000,000,000, you given N (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 first).

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 M.

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?

On a number line of length M, where 0 < M <= 1,000,000,000, you given N (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 first).

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 M.

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?

Here's an interesting question I came upon:

Let's just say on a number line of length M, where 0 < M <= 1,000,000,000, you given N (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 first).

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 M.

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 (can't post images on programmers because I don't have enough rep) : https://i.sstatic.net/zRv4Q.png

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?

Here's an interesting question I came upon:

Let's just say on a number line of length M, where 0 < M <= 1,000,000,000, you given N (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 first).

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 M.

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?

Note: I originally posted this on StackOverflow, but was told this would be a better spot.

Here's an interesting question I came upon:

Let's just say on a number line of length M, where 0 < M <= 1,000,000,000, you given N (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 first).

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 M.

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 (can't post images on programmers because I don't have enough rep) : https://i.sstatic.net/zRv4Q.png

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?

Here's an interesting question I came upon:

Let's just say on a number line of length M, where 0 < M <= 1,000,000,000, you given N (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 first).

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 M.

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 (can't post images on programmers because I don't have enough rep) : https://i.sstatic.net/zRv4Q.png

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?