1066 - Campus Bikes II (Medium)

Problem Link

https://leetcode.com/problems/campus-bikes-ii/

Problem Statement

On a campus represented as a 2D grid, there are n workers and m bikes, with n <= m. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Example 1:

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 is 3, so the output is 6.

Example 2:

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.

Example 3:

Input: workers = [[0,0],[1,0],[2,0],[3,0],[4,0]], bikes = [[0,999],[1,999],[2,999],[3,999],[4,999]]
Output: 4995

Constraints:

• n == workers.length
• m == bikes.length
• 1 <= n <= m <= 10
• workers[i].length == 2
• bikes[i].length == 2
• 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
• All the workers and the bikes locations are unique.

Approach 1: DP Bit Masking

Iterate each mask from $0$ to $m$ where $m$ is the size of $bikes$. For each mask, we try to find each bike that is not in use and calculate the Manhattan distance and try the next $workerIdx$. We memorise the result to speed up the whole process.

Written by @wingkwong

class Solution {
public:
    vector<int> dp;
    int n, m;
    int dfs(vector<vector<int>>& workers, vector<vector<int>>& bikes, int workerIdx, int mask) {
        // worker idx out of range
        if (workerIdx >= n) return 0;
        // calculated before, return immediately
        if (dp[mask] != -1) return dp[mask];
        // init res
        int res = INT_MAX;
        // iterate each mask
        for (int bikeIdx = 0; bikeIdx < m; bikeIdx++) {
            // this bike is not in use
            if (!(mask & (1 << bikeIdx))) {
                // calculate the Manhattan distance
                int dist = abs(workers[workerIdx][0] - bikes[bikeIdx][0]) + abs(workers[workerIdx][1] - bikes[bikeIdx][1]);
                res = min(res, dist + dfs(workers, bikes, workerIdx + 1, mask | (1 << bikeIdx)));
            }
        }
        // memoize the smallest distance sum for this mask
        return dp[mask] = res;
    }
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        n = workers.size(), m = bikes.size();
        dp = vector<int>(1 << m, -1);
        return dfs(workers, bikes, 0, 0);
    }
};

We can also write like this.

Written by @wingkwong

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int n = workers.size(), m = bikes.size(), ans = 1e9;
        vector<int> dp(1 << m, 1e9);
        dp[0] = 0;
        // iterate each mask
        for (int mask = 0; mask < (1 << m); mask++) {
            // worker idx
            int workerIdx = __builtin_popcount(mask);
            // all workers got the bikes
            // update the answer
            if (workerIdx >= n) {
                ans = min(ans, dp[mask]);
                continue;
            }
            // iterate each bike
            for (int bikeIdx = 0; bikeIdx < m; bikeIdx++) {
                // this bike is not in use
                if (!(mask & (1 << bikeIdx))) {
                    // calculate the Manhattan distance
                    int dist = abs(workers[workerIdx][0] - bikes[bikeIdx][0]) + abs(workers[workerIdx][1] - bikes[bikeIdx][1]);
                    // new mask = current mask + this bike
                    int newMask = mask | (1 << bikeIdx);
                    // update distance sum
                    dp[newMask] = min(dp[newMask], dist + dp[mask]);
                }
            }
        }
        return ans;
    }
};