
Input: workers =[[0,0],[2,1]], bikes =[[1,2],[3,3]] Output:6 Explanation: We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is3, so the output is6.
Example 2:
1
2
3
4
5

Input: workers =[[0,0],[1,1],[2,0]], bikes =[[1,0],[2,2],[2,1]] Output:4 Explanation: We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.
We want to assign each worker a unique bike such that the total Manhattan distance is minimized. Since n ≤ m and n ≤ 10, we can use bitmask dynamic programming to efficiently try all assignments and cache results.
classSolution {
public:int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int n = workers.size(), m = bikes.size();
vector<vector<int>> memo(n, vector<int>(1<< m, -1));
function<int(int, int)> dp = [&](int i, int mask) {
if (i == n) return0;
if (memo[i][mask] !=-1) return memo[i][mask];
int ans = INT_MAX;
for (int j =0; j < m; ++j) {
if (!(mask & (1<< j))) {
int d = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
ans = min(ans, d + dp(i +1, mask | (1<< j)));
}
}
return memo[i][mask] = ans;
};
returndp(0, 0);
}
};
classSolution {
funassignBikes(workers: Array<IntArray>, bikes: Array<IntArray>): Int {
val n = workers.size
val m = bikes.size
val memo = Array(n) { IntArray(1 shl m) { -1 } }
fundp(i: Int, mask: Int): Int {
if (i == n) return0if (memo[i][mask] != -1) return memo[i][mask]
var ans = Int.MAX_VALUE
for (j in0 until m) {
if ((mask and (1 shl j)) ==0) {
val d = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1])
ans = minOf(ans, d + dp(i + 1, mask or (1 shl j)))
}
}
memo[i][mask] = ans
return ans
}
return dp(0, 0)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defassignBikes(self, workers: list[list[int]], bikes: list[list[int]]) -> int:
from functools import lru_cache
n, m = len(workers), len(bikes)
@lru_cache(None)
defdp(i: int, mask: int) -> int:
if i == n:
return0 ans = float('inf')
for j in range(m):
ifnot (mask & (1<< j)):
d = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
ans = min(ans, d + dp(i +1, mask | (1<< j)))
return ans
return dp(0, 0)