Problem explanation

In this problem, we have a number of workers and bikes on a 2D grid, each represented by a coordinate (x, y). The aim is to assign one unique bike to each worker in a way that minimizes the total Manhattan distances between each worker and their assigned bike.

The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as absolute(x1 - x2) + absolute(y1 - y2).

For example: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] Here, if we assign bike 0 to worker 0, bike 2 to worker 1 and bike 1 to worker 2, the sum of Manhattan distances would be 1 (for worker 0), 2 (for worker 1) and 1 (for worker 2), adding up to a total of 4.

Approach

This problem can be solved using recursive approach and bit manipulation.

We will initialize the total minimum sum as infinity (INT_MAX) and iterate through each bike. If a bike is not already used (checked using bit mask), we will calculate the Manhattan distance of the current worker to the bike and add it to the recursive call for the next worker with the updated bike used status. The total minimum sum will be updated with the minimum value of the current sum and the calculated sum.

This will be done using depth-first search (DFS) approach, where we start from the first worker and go through each possible assignment, recursively going to the next worker until all workers have been assigned a bike. The minimum sum calculated in this process is our answer.

Python Solution

1
2python
3class Solution:
4    def assignBikes(self, workers, bikes):
5            n, m = len(workers), len(bikes)
6            # Initialization of memoization table
7            dp = [[0]*1024 for _ in range(n+1)]
8            return self.dfs(workers, bikes, 0, 0, dp)
9
10    def dist(self, w, b):
11        return abs(w[0]-b[0]) + abs(w[1]-b[1])
12        
13    def dfs(self, workers, bikes, i, used, dp):
14        # If we achieve the number of total workers=>return zero
15        if i == len(workers): return 0
16        if dp[i][used] > 0: return dp[i][used]
17        
18        res = float('inf')
19        for j in range(len(bikes)):
20            # Check if the bike is already used or not and calculate the minimum distances
21            if (used>>j)&1 == 0:
22                res = min(res, self.dist(workers[i], bikes[j]) + self.dfs(workers, bikes, i+1, used|(1<<j), dp))
23        # Update the memoization table
24        dp[i][used] = res
25        return res

Time complexity

The time complexity would be O(NM2^N) where N is the number of workers and M is the number of bikes. This is because for each worker, we are iterating through each bike and checking all possible combinations of assignments. This results in a time complexity that is exponential with respect to the number of workers. The space complexity would be O(N*2^N) due to the memoization table used to avoid recalculations.# JavaScript Solution

Here is the same algorithm implemented in JavaScript:

1
2javascript
3class Solution {
4    constructor() {
5        this.dp = Array(1025).fill(Number.MAX_VALUE);
6        this.workers = null;
7        this.bikes = null;
8    }
9    
10    _dist(w, b) {
11        return Math.abs(w[0] - b[0]) + Math.abs(w[1] - b[1]);
12    }
13
14    _dfs(i, mask) {
15        if (i >= this.workers.length) return 0;
16        if (this.dp[mask] !== Number.MAX_VALUE) return this.dp[mask];
17
18        for (let j = 0; j < this.bikes.length; j++) {
19            if(!(mask & (1 << j))) {
20                this.dp[mask] = Math.min(this.dp[mask], this._dist(this.workers[i], this.bikes[j]) + this._dfs(i + 1, mask | (1 << j)));
21            }
22        }
23        return this.dp[mask];
24    }
25
26    assignBikes(workers, bikes) {
27        this.workers = workers;
28        this.bikes = bikes;
29        return this._dfs(0, 0);
30    }
31};

Java Solution

The same algorithm applies for Java as well:

1
2java
3class Solution {
4    int[] dp;
5    int[][] workers, bikes;
6
7    public int assignBikes(int[][] workers, int[][] bikes) {
8        this.workers = workers;
9        this.bikes = bikes;
10        dp = new int[1 << bikes.length];
11        Arrays.fill(dp, Integer.MAX_VALUE);
12        return dfs(0, 0);
13    }
14
15    int dfs(int i, int mask) {
16        if(i == workers.length)
17            return 0;
18
19        if(dp[mask] != Integer.MAX_VALUE)
20            return dp[mask];
21        
22        for (int j = 0; j < bikes.length; ++j)
23            if ((mask & (1 << j)) == 0)
24                dp[mask] = Math.min(dp[mask], dist(workers[i], bikes[j]) + dfs(i + 1, mask | (1 << j)));
25        return dp[mask];
26    }
27    
28    int dist(int[] w, int[] b) {
29        return Math.abs(w[0] - b[0]) + Math.abs(w[1] - b[1]);
30    }
31}

Time complexity

The time complexity of the JavaScript and Java solutions is similar to the Python solution, with O(NM2^N) where N is the number of workers and M is the number of bikes. This is due to the iterative calculation of the Manhattan distance for each worker and bike pair, and the recursive calls to the depth-first search procedure.

The space complexity is also equivalent, standing at O(N*2^N), which is the size of the memoization array that is utilized to store the intermediate results and prevent repetitive calculations.