Campus Bikes II

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;
	}
};

The solution implements an approach to assign bikes to workers such that the sum of the Manhattan distances between each worker and their assigned bike is minimized. This problem is tackled using a priority queue to facilitate the selection of minimum distances, and a bitmask to represent the assignment state of bikes, optimizing the approach further with an unchecked state tracking via a set.

• The calcDistance function calculates the Manhattan distance between two points. It takes two vectors, coordsA and coordsB, representing the coordinates of a worker and a bike, respectively.

• The bitCount function counts the number of set bits in an integer. This represents the number of bikes that have been assigned to workers.

• assignBikes is the core function where:

  1. It initializes a priority queue which is used to always extend the pair of current total distance and the bitmask representing bike assignments that has the smallest distance.
  2. A set named processed is maintained to avoid reprocessing the same bitmask.
  3. Continuously, it pops elements from the priority queue, checks and processes them. If the bitmask indicates all workers have been assigned bikes, the current distance sum is returned as the result.
  4. For each unassigned bike, the function calculates the new distance if that bike were assigned to the current worker and then pushes this new distance and updated bitmask back into the priority queue.

This solution leverages bit manipulation and a min-heap to effectively and efficiently solve the problem by considering each possible allocation of bikes to workers, ensuring that each combination is processed in an order that first considers the lowest cumulative distance.

class Solution {
    private int calculateDistance(int[] worker, int[] bike) {
        return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
    }
    
    private int bitCount(int number) {
        int count = 0;
        while (number != 0) {
            number &= (number - 1);
            count++;
        } 
        return count;
    }
    
    public int assignBikes(int[][] workers, int[][] bikes) {
        int totalBikes = bikes.length, totalWorkers = workers.length;
        
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        Set<Integer> visitedMasks = new HashSet<>();

        priorityQueue.add(new int[]{0, 0});
        while (!priorityQueue.isEmpty()) {
            int[] top = priorityQueue.poll();
            int distSum = top[0], mask = top[1];
            
            if (visitedMasks.contains(mask))
                continue;
            
            visitedMasks.add(mask);
            int workerID = bitCount(mask);
            
            if (workerID == totalWorkers) {
                return distSum;
            }

            for (int bikeID = 0; bikeID < totalBikes; bikeID++) {
                if ((mask & (1 << bikeID)) == 0) {
                    int newDistSum = distSum + 
                        calculateDistance(workers[workerID], bikes[bikeID]);
                    
                    int newMask = mask | (1 << bikeID);
                    priorityQueue.add(new int[]{newDistSum, newMask});
                }
            }
        }
        
        return -1;
    }
}

This program in Java solves the problem of assigning bikes to workers in such a way that the total distance traveled by all workers is minimized. It efficiently uses a bit manipulation technique to represent combinations of bike assignments to workers, combined with a priority queue to ensure the smallest distance sum is prioritized for expansion. Here's how the solution is structured:

1. Helper Methods:

   • calculateDistance: Computes the Manhattan distance between a worker and a bike.
   • bitCount: Counts the number of 1s in the binary representation of the number, representing how many bikes have been assigned.

2. Core Method - assignBikes:

   • Initializes a PriorityQueue to store and retrieve states by minimum distance sum using a comparator.
   • Uses a Set to avoid revisiting already checked combinations of bike assignments, exploiting properties of bit masks to represent these combinations.
   • Continuously expands the state with the smallest distance sum by trying to assign unassigned bikes to the next worker. Each state is a pair of the current distance sum and the bitmask representing which bikes have been assigned.

3. Efficiency Considerations:

   • By stopping the expansion as soon as all workers have bikes assigned (workerID == totalWorkers), the algorithm ensures an optimal solution is found as soon as possible.
   • Using bit manipulation (via masks) provides a compact and efficient way to handle the combinations of assignments.

This approach ensures a focused, step-by-step examination of possible assignments, using both bit-level operations for efficiency and a priority-based exploration to ensure the minimum distance configuration is found swiftly.