People and Cakes II
A hallway is a list of cells: 0 empty, 1 a person, 2 a cake. Give every person a distinct cake so that the total walking distance is as small as possible. There are at least as many cakes as people.
Return [total, pairs]: the minimum total distance and the assignment as [personIndex, cakeIndex] pairs, one per person, in any order. Any assignment with the minimum total is accepted.
assignCakes([1, 2, 0, 1, 0, 0, 2]) -> [4, [[0, 1], [3, 6]]]
Here both people are closest to the cake at index 1; sending the person at index 3 to the cake at index 6 is what makes the total 4.
Hints
Hint 1
Greedy nearest-cake fails as soon as two people want the same cake. Work with the sorted index lists of people and cakes instead.
Hint 2
In an optimal matching no two assignments cross, so dp[i][j] = cheapest way to seat the first i people using only the first j cakes: either cake j is skipped, or person i takes cake j.
Hint 3
Recover the pairs by walking the table backwards: when dp[i][j] equals dp[i][j - 1] the cake was skipped, otherwise person i took it.