So this is an algorithm question. The problem statement is the following: given two lists of coordinates (or length n each) of bikes and people on a 2D grid (or a 2D grid that show the positions of each bike and person), calculate the optimal pairing of the bikes and people so that the total Manhattan distance of all the pairs are minimized. It is guaranteed that for each person, the distance to all bikes won't be the same and same applies for each bikes.
There is a solution in this question, which states that we can sort all the distances from low to high and pair the bike to the person if they are both unpaired. The complexity is obviously O(n^2 logn) time and O(n^2) space.
So my questions are
Update:
The question linked is using a different criteria of priority. So what would be the algorithm that calculates the optimal pairing if the criteria is minimizing total Manhattan distance (except for the brute force DFS algorithm that is exponential in complexity)?
Update 2:
If the criteria is that no pair would prefer each other than their current partner, then it's a stable marriage problem. If the criteria is the total sum of distances, Hungarian algorithm should be used.
The sorting algorithm computes a stable marriage, because whenever a pair is formed, every neighbor is either available or in a pairing of no lesser desirability.
Stable marriage is not optimal. The bike and person at distance 2 would rather be with each other, which forces the pairing of the bike and the person at distance 9. The total cost is 11, which is worse than 3 + 4 = 7.
B
2 |3
B---P
|4
P
An optimal algorithm is to compute pairwise distances and run the Hungarian algorithm to compute a minimum-cost perfect matching.