Given this problem:
You have a warehouse with M containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be 1 meter apart. You also have 2 robots that can pick up 1 piece of candy and transport it between any two containers.
The robots take instructions in the form of queries consisting of two integers, Ma and Mb, respectively. To execute a query, a robot travels to container Ma, picks up 1 candy, transports it to container Mb, and then stops at Mb until it receives another query.
Calculate the minimum total distance the robots must travel to execute N queries in order.
Note: You choose which robot executes each query.
Initially I assumed that I should simply choose the robot which is closer to carry out the move, but this approach fails in some test cases, could anyone explain why this approach is not valid for all cases, and what is the right approach, Thanks.
Sample input and expected output here.
The problem is in the Dynamic programming category, and you yourself tagged your question greedy (your approach is indeed greedy). There will be cases when the minimum distance for a given query (local minimum) is not optimal for the full set of queries (global minimum). Hence you need to consider all possible assignments of robots to queries, but with DP techniques this is not an exhaustive search.
I don't want to detail the exact solution for you, since there are plenty of resources online on DP (make a 2-dimensional table of costs, moving across columns = robot 1, moving across rows = robot 2, find optimal path through the table, …). But I want to show you an example situation where the greedy approach is sub-optimal.
A robot 1B robot 2F start point of queryT end point of querySolved with the greedy approach:
(A) B
1 . . F . T . . . . . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
(A) B
2 . . . . . . F . T . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
(A) B
3 F T . . . . . . . . . // A is closer to F, travels 8 (to F) + 1 (to T) = 9
A B
Total distance traveled: 4 + 4 + 9 = 17.
An optimal approach (there may be multiple):
(A) B
1 . . F . T . . . . . . // A takes query, travels 2 (to F) + 2 (to T) = 4
A (B)
2 . . . . . . F . T . . // B takes query, travels 4 (to F) + 2 (to T) = 6
(A) B
3 F T . . . . . . . . . // A takes query, travels 4 (to F) + 1 (to T) = 5
A B
Total distance traveled: 4 + 6 + 5 = 15.
Note that B took the second query even though it was not the closest to the start point.