1. If you're empty, start moving to the right.

2. Whenever you reach an object and you're empty, pick it up (duh) and move toward its destination.

3. Whenever you reach an object a and you're already carrying b, always choose whichever of the objects has the numerically smallest destination (furthest to the left).

4. If you're not yet at M, go back to step 1.

This is optimal: The only place where you have a real choice is in step 3. Handling the leftmost destination first ensures that by the time you've dispatched both objects, you'll be as far to the right as possible.

Why is this question on programmers.sx? Yes, "interview question", but it's just a nice riddle.

1. If you're empty, start moving to the right.

2. Whenever you reach an object and you're empty, pick it up (duh) and move toward its destination.

3. Whenever you reach an object a and you're already carrying b, always choose whichever of the objects has the numerically smallest destination (furthest to the left).

4. If you're not yet at M, go back to step 1.

This is optimal: The only place where you have a real choice is in step 3. Handling the leftmost destination first ensures that by the time you've dispatched both objects, you'll be as far to the right as possible.

Why is this question on programmers.sx? Yes, "interview question", but it's just a nice riddle.

PS. In terms of implementation, all you need is the list of tasks (the integer pairs of points) sorted by original position.

1. Start moving to the right.

2. Whenever you reach an object and you're empty, pick it up (duh) and move toward its destination.

3. Whenever you reach an object a and you're already carrying b, always choose whichever of the objects has the numerically smallest destination (furthest to the left).

4. Go back to step 1 (until you reach M).

This is optimal: The only place when you have a real choice is in step 3. Choosing the leftmost destination first ensures that by the time you've dispatched both objects, you'll be as far to the right as possible.

Why is this question on programmers.sx? Yes, "interview question", but it's just a nice riddle.

1. If you're empty, start moving to the right.

2. Whenever you reach an object and you're empty, pick it up (duh) and move toward its destination.

3. Whenever you reach an object a and you're already carrying b, always choose whichever of the objects has the numerically smallest destination (furthest to the left).

4. If you're not yet at M, go back to step 1.

This is optimal: The only place where you have a real choice is in step 3. Handling the leftmost destination first ensures that by the time you've dispatched both objects, you'll be as far to the right as possible.

Why is this question on programmers.sx? Yes, "interview question", but it's just a nice riddle.