Campus Bikes II

Problem Statement

In a scenario where a campus is depicted as a 2D grid, there exist n workers and m bikes, with the relationship n <= m. Both the workers and bikes are represented as two-dimensional coordinates on the grid. The main objective is to allocate exactly one unique bike to each worker. This pairing must be done such that the collective sum of the Manhattan distances between each worker and their assigned bike is as minimized as possible. The Manhattan distance between two points, say p1 and p2, is calculated using the formula: Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. The task is to determine and return the minimal possible sum of these distances for the optimal assignments.

Examples

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 and Intuition

The problem at hand requires an optimal assignment of bikes to workers such that the total Manhattan distance is minimized. Here's an intuitive approach based on the examples and constraints provided:

1. Understanding Distance Calculation:

   • The Manhattan distance is chosen because it effectively measures the grid-based path between any two points in a linear city-like block layout.

2. Example Walk-throughs:

   • For Example 1, with two workers and two bikes:
     • Calculate distance from each worker to each bike.
     • The optimal assignment by manual inspection or algorithmic design leads to each worker paired such that total distance is minimized to 6.
   • For Example 2, the scenario of three workers and three bikes again shows:
     • Calculation of possible distances and then deciding on distribution optimizing the sum of distances. A few assignment trials provide a minimal sum of 4.
   • Example 3 demonstrates distance minimization with aligned workers and far distant bikes, yielding a straightforward but large distance sum of 4995.

3. Constraint Utilization:

   • Given that the number of workers and bikes can be at most 10, an exhaustive approach or an optimized algorithm using backtracking or the Hungarian algorithm (also known as the Munkres or Kuhn-Munkres algorithm) could be feasible. These methods work by ensuring each potential assignment's feasibility and optimality under the given constraints.
   • Unique positions of workers and bikes simplify the calculation as there won't be duplicate positions which could potentially complicate the pairing mechanism, ensuring that each worker-bike pair is distinctly calculated without overlaps.

This task, though computationally intensive for large numbers, remains computationally feasible for the upper constraints specified, by leveraging combinatorial optimization techniques particularly suited to such assignment problems.

Solutions

class Solution {
public:
    int calcDistance(vector<int>& coordsA, vector<int>& coordsB) {
        return abs(coordsA[0] - coordsB[0]) + abs(coordsA[1] - coordsB[1]);
    }
        
    int bitCount(int bitmask) {
        int total = 0;
        while (bitmask != 0) {
            bitmask &= (bitmask - 1);
            total++;
        }
        return total;
    }
        
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int totalBikes = bikes.size();
        int totalWorkers = workers.size();
            
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        unordered_set<int> processed;
    
        minHeap.push({0, 0});
        while (!minHeap.empty()) {
            int distSum = minHeap.top().first;
            int mask = minHeap.top().second;
            minHeap.pop();
                
            if (processed.find(mask) != processed.end())
                continue;
                
            processed.insert(mask);
            int currentWorker = bitCount(mask);
                
            if (currentWorker == totalWorkers)
                return distSum;
    
            for (int bikeIdx = 0; bikeIdx < totalBikes; bikeIdx++) {
                if (!(mask & (1 << bikeIdx))) {
                    int newDistSum = distSum + 
                        calcDistance(workers[currentWorker], bikes[bikeIdx]);
                    int newMask = mask | (1 << bikeIdx);
                    minHeap.push({newDistSum, newMask});
                }
            }
        }
            
        return -1;
	}
};