Campus Bikes II

medium dynamic programming bitmask assignment

Problem

On a campus there are n workers and m bikes, with n ≤ m. Each worker and bike has a 2D location. Assign each worker a distinct bike so that the sum of Manhattan distances between every worker and their assigned bike is as small as possible. The Manhattan distance between (x1, y1) and (x2, y2) is |x1 − x2| + |y1 − y2|. Return that minimum possible total.

Inputworkers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]

Output6

Worker 0 → bike 0 costs |0−1|+|0−2| = 3; worker 1 → bike 1 costs |2−3|+|1−3| = 3; total 6. The swapped pairing costs 6 + 2 = 8, so 6 is the minimum.

workers (e.g. 0,0; 2,1)

bikes (e.g. 1,2; 3,3)

def assign_bikes(workers, bikes):
    n, m = len(workers), len(bikes)
    INF = float("inf")
    dp = [INF] * (1 << m)
    dp[0] = 0
    for mask in range(1 << m):
        w = bin(mask).count("1")        # next worker to place
        if dp[mask] == INF or w >= n:
            continue
        for b in range(m):
            if mask & (1 << b):
                continue
            d = abs(workers[w][0] - bikes[b][0]) + abs(workers[w][1] - bikes[b][1])
            nxt = mask | (1 << b)
            dp[nxt] = min(dp[nxt], dp[mask] + d)
    return min(dp[mask] for mask in range(1 << m)
               if bin(mask).count("1") == n)

function assignBikes(workers, bikes) {
  const n = workers.length, m = bikes.length, INF = Infinity;
  const dp = new Array(1 << m).fill(INF);
  dp[0] = 0;
  for (let mask = 0; mask < (1 << m); mask++) {
    const w = popcount(mask);          // next worker to place
    if (dp[mask] === INF || w >= n) continue;
    for (let b = 0; b < m; b++) {
      if (mask & (1 << b)) continue;
      const d = Math.abs(workers[w][0] - bikes[b][0])
              + Math.abs(workers[w][1] - bikes[b][1]);
      const nxt = mask | (1 << b);
      dp[nxt] = Math.min(dp[nxt], dp[mask] + d);
    }
  }
  let best = INF;
  for (let mask = 0; mask < (1 << m); mask++)
    if (popcount(mask) === n) best = Math.min(best, dp[mask]);
  return best;
}
function popcount(x){let c=0;while(x){c+=x&1;x>>=1;}return c;}

class Solution {
    public int assignBikes(int[][] workers, int[][] bikes) {
        int n = workers.length, m = bikes.length, INF = 1 << 29;
        int[] dp = new int[1 << m];
        java.util.Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << m); mask++) {
            int w = Integer.bitCount(mask);     // next worker to place
            if (dp[mask] == INF || w >= n) continue;
            for (int b = 0; b < m; b++) {
                if ((mask & (1 << b)) != 0) continue;
                int d = Math.abs(workers[w][0] - bikes[b][0])
                      + Math.abs(workers[w][1] - bikes[b][1]);
                int nxt = mask | (1 << b);
                dp[nxt] = Math.min(dp[nxt], dp[mask] + d);
            }
        }
        int best = INF;
        for (int mask = 0; mask < (1 << m); mask++)
            if (Integer.bitCount(mask) == n) best = Math.min(best, dp[mask]);
        return best;
    }
}

int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
    int n = workers.size(), m = bikes.size(), INF = 1 << 29;
    vector<int> dp(1 << m, INF);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int w = __builtin_popcount(mask);   // next worker to place
        if (dp[mask] == INF || w >= n) continue;
        for (int b = 0; b < m; b++) {
            if (mask & (1 << b)) continue;
            int d = abs(workers[w][0] - bikes[b][0])
                  + abs(workers[w][1] - bikes[b][1]);
            int nxt = mask | (1 << b);
            dp[nxt] = min(dp[nxt], dp[mask] + d);
        }
    }
    int best = INF;
    for (int mask = 0; mask < (1 << m); mask++)
        if (__builtin_popcount(mask) == n) best = min(best, dp[mask]);
    return best;
}

Explanation

We need to pair each worker with a distinct bike so the total distance is smallest. Trying every pairing by hand explodes fast, so we use a bitmask to remember which bikes are already taken and build the answer one worker at a time.

The key insight: dp[mask] = the least total distance to place the first few workers using exactly the bikes whose bits are set in mask. The number of set bits, popcount(mask), tells us how many workers are placed, and therefore which worker comes next.

For each reachable mask, we look at worker w = popcount(mask) and try giving them every still-free bike b. The new state is nxt = mask | (1 << b), and we update dp[nxt] = min(dp[nxt], dp[mask] + d) where d is that worker-to-bike Manhattan distance.

Because a worker is only assigned once and each bike bit is set once, every valid assignment is counted exactly once. The answer is the smallest dp[mask] among masks that use exactly n bikes.

Example: with workers [[0,0],[2,1]] and bikes [[1,2],[3,3]], pairing worker 0 to bike 0 (cost 3) then worker 1 to bike 1 (cost 3) gives 6, which beats the swapped pairing, so the answer is 6.

Time: O(m · 2^m) Space: O(2^m)