DSA problem
Campus Bikes II
On a campus represented as a 2D grid, you are given a list workers of length n and a list bikes of length m (with m >= n). Each worker and bike has an (x, y) coordinate. You must assign each worker exactly one distinct bike so that the sum of Manhattan distances between every worker and their assigned bike is minimized. Return that minimum total distance.
A brute-force permutation search would explore m! / (m - n)! assignments, which is infeasible. The standard speedup uses bitmask DP over the set of used bikes. Let dp[mask] be the minimum cost to assign workers 0, 1, ..., popcount(mask) - 1 to exactly the bikes selected by mask. The next worker to consider is determined entirely by the popcount, so we never need a separate index.
Starting from dp[0] = 0, for each mask we try assigning worker w = popcount(mask) to any unused bike b (bit b not in mask) and relax dp[mask | (1 << b)] = min(..., dp[mask] + |w.x - b.x| + |w.y - b.y|). The final answer is the minimum dp[mask] over all masks with exactly n bits set.
Because n <= 10 and m <= 10, the mask space is at most 2^{10} = 1024 and each state explores up to m transitions, giving O(2^m * m) work — fast and clean. Distances are precomputed in an n × m table to avoid recomputing absolute values inside the DP loop.
Examples
workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]6workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]4workers = [[0,0]], bikes = [[5,5]]10Constraints
- n == workers.length
- m == bikes.length
- 1 <= n <= m <= 10
- workers[i].length == bikes[j].length == 2
- 0 <= workers[i][0], workers[i][1] < 1000
- 0 <= bikes[j][0], bikes[j][1] < 1000
- All bikes and all workers have distinct positions.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.