Campus Bikes

Problem Statement

In a two-dimensional space representing a campus plane, each point is either occupied by a worker or a bike. The goal is to assign bikes to workers efficiently based on their proximity. Specifically, you need to determine an assignment such that every worker acquires a bike based on the shortest Manhattan distance, which is defined as the absolute differences in their x and y coordinates. This task is represented by the arrays workers and bikes, containing respective positions.

To manage ties where distances are identical, you are to prioritize assignment by the smallest worker index, and if the conflict persists, by the smallest bike index. The process continues in a structured manner until every worker has been assigned a bike. The solution should be returned as an array where each index represents a worker and each value corresponds to the index of the bike they've been assigned.

Examples

Example 1

Input:

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

Output:

[1,0]

Explanation:

Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].

Example 2

Input:

workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]

Output:

[0,2,1]

Explanation:

Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

Constraints

• n == workers.length
• m == bikes.length
• 1 <= n <= m <= 1000
• workers[i].length == bikes[j].length == 2
• 0 <= xi, yi < 1000
• 0 <= xj, yj < 1000
• All worker and bike locations are unique.

Approach and Intuition

To solve this problem effectively:

1. Understanding Distance Calculation:

   • The key metric used for determining the closest bike to a worker is the Manhattan distance, a straightforward absolute difference measure in horizontal and vertical directions.

2. Data Structure Choice:

   • Utilizing a min-heap or priority queue can help efficiently manage and retrieve the shortest distance assignments. This structure makes it easier to handle multiple cases based on distance, worker index, and bike index efficiently due to its inherent property of sorting.

3. Step-by-Step Assignment:

   • First, compute the distance between every worker and bike, and store these values in the min-heap, tagged with worker and bike indices.
   • Extract from this heap to get the shortest distance assignments while adhering to the priority rules specified—smallest worker index first, then smallest bike index.
   • Ensure bikes are marked as assigned once a worker is paired with a bike.

4. Iterations:

   • Iterate over the worker-bike pair combinations to compute the initial distances.
   • Continuously process the heap to resolve the optimal pairing, and then update the respective statuses of the workers and bikes.

5. Edge Cases:

   • Handle situations where the number of bikes is exactly equal to the number of workers, making sure every worker gets a bike.
   • Address potential boundary problems like workers or bikes being placed on the extreme edges of the allowable plane coordinate limits.

Implementing this solution effectively ensures that each worker receives the closest possible bike according to the problem's rules, with tie-breaking managed through index precedence, demonstrating a keen blend of algorithmic strategy and data structure application.

Solutions

class Solution {
public:
    int calcDistance(vector<int>& pos1, vector<int>& pos2) {
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]);
    }
        
    vector<int> bikeAssignment(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        vector<vector<tuple<int, int, int>>> workerBikeDistList;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> minHeap;
            
        for (int i = 0; i < workers.size(); i++) {
            vector<tuple<int, int, int>> distances;
            for (int j = 0; j < bikes.size(); j++) {
                int dist = calcDistance(workers[i], bikes[j]);
                distances.emplace_back(dist, i, j);
            }
            sort(distances.begin(), distances.end(), greater<tuple<int, int, int>>());
            minHeap.push(distances.back());
            distances.pop_back();
            workerBikeDistList.push_back(distances);
        }
    
        vector<int> bikeTaken(bikes.size(), false);
        vector<int> workerBike(workers.size(), -1);
            
        while (!minHeap.empty()) {
            auto[dist, worker, bike] = minHeap.top();
            minHeap.pop();
            if (!bikeTaken[bike]) {
                bikeTaken[bike] = true;
                workerBike[worker] = bike;
            } else {
                minHeap.push(workerBikeDistList[worker].back());
                workerBikeDistList[worker].pop_back();
            }
        }
            
        return workerBike;
    }
};