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.lengthm == bikes.length1 <= n <= m <= 1000workers[i].length == bikes[j].length == 20 <= xi, yi < 10000 <= xj, yj < 1000- All worker and bike locations are unique.
Approach and Intuition
To solve this problem effectively:
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.
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.
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.
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.
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
- C++
- Java
- Python
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;
}
};
The C++ program provided solves the problem of assigning bikes to workers based on proximity on a campus. The solution uses a combination of priority queues and vectors to efficiently assign the closest bike to each worker in such a way that each bike is assigned only once. Here is the breakdown of how the program achieves this:
The function
calcDistancecalculates the Manhattan distance between a worker and a bike. This distance is simply the sum of the absolute differences in their x and y coordinates.The main function
bikeAssignmentaccepts two 2D vectors, one for workers and one for bikes, and proceeds to calculate the distance from each worker to each bike, associating these distances with corresponding worker and bike indices.For each worker, all distances to every bike are stored in a min-heap to ensure that the closest bike is always prioritized for assignment.
The solution maintains arrays to keep track of which bikes have been taken and the bike assigned to each worker. The program iterates over the min-heap to assign the closest available bike to each worker until all workers have a bike allocated.
If a bike is already taken, the next closest bike is reconsidered by fetching from the back of the sorted list.
By utilizing priority queues and dynamic arrays, the program efficiently handles the assignments while ensuring the minimization of distances between assigned bikes and workers. This solution works well for scenarios where the number of workers and bikes are relatively manageable, and simple distance metrics like Manhattan distances are suitable for the context of the problem.
class Assignment {
List<List<Pair<Integer, Integer>>> workerBikes = new ArrayList<>();
int[] assignedBikeIndex = new int[1001];
class WorkerBikeDistance {
int workerId;
int bikeId;
int dist;
WorkerBikeDistance(int workerId, int bikeId, int dist) {
this.workerId = workerId;
this.bikeId = bikeId;
this.dist = dist;
}
}
Comparator<WorkerBikeDistance> distanceComparator = new Comparator<WorkerBikeDistance>() {
@Override
public int compare(WorkerBikeDistance x, WorkerBikeDistance y) {
if (x.dist != y.dist) {
return x.dist - y.dist;
} else if (x.workerId != y.workerId) {
return x.workerId - y.workerId;
} else {
return x.bikeId - y.bikeId;
}
}
};
int calculateDistance(int[] worker, int[] bike) {
return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
}
void assignNextBike(PriorityQueue<WorkerBikeDistance> priorityQueue, int worker) {
Pair<Integer, Integer> nextBike = workerBikes.get(worker).get(assignedBikeIndex[worker]);
assignedBikeIndex[worker]++;
WorkerBikeDistance newPair =
new WorkerBikeDistance(worker, nextBike.getValue(), nextBike.getKey());
priorityQueue.add(newPair);
}
public int[] matchWorkersAndBikes(int[][] workers, int[][] bikes) {
PriorityQueue<WorkerBikeDistance> pq = new PriorityQueue<>(distanceComparator);
for (int worker = 0; worker < workers.length; worker++) {
List<Pair<Integer, Integer>> listBikeDistances = new ArrayList<>();
for (int bike = 0; bike < bikes.length; bike++) {
int dist = calculateDistance(workers[worker], bikes[bike]);
listBikeDistances.add(new Pair(dist, bike));
}
Collections.sort(listBikeDistances, Comparator.comparing(Pair::getKey));
workerBikes.add(listBikeDistances);
assignedBikeIndex[worker] = 0;
assignNextBike(pq, worker);
}
boolean[] isBikeAssigned = new boolean[bikes.length];
int[] workersAssignment = new int[workers.length];
Arrays.fill(workersAssignment, -1);
while (!pq.isEmpty()) {
WorkerBikeDistance current = pq.remove();
int worker = current.workerId;
int bike = current.bikeId;
if (workersAssignment[worker] == -1 && !isBikeAssigned[bike]) {
isBikeAssigned[bike] = true;
workersAssignment[worker] = bike;
} else {
assignNextBike(pq, worker);
}
}
return workersAssignment;
}
}
In this Java solution, the task is to optimally match workers to bikes based on their proximity. The process involves several key components:
Data Structures:
WorkerBikeDistance: A custom class representing the distance between a worker and a bike, along with identifiers for both.workerBikes: AnArrayListcontaining a list of bike distances and bike indices for each worker.assignedBikeIndex: An array to track which bike a worker considers next.
Distance Calculation: The method
calculateDistancecomputes the Manhattan distance between a worker and a bike. This value is used to populate distance lists withinworkerBikes.Priority Queue and Sorting:
- A priority queue (
PriorityQueue<WorkerBikeDistance>) is initialized with a comparator to ensure the bike with the smallest distance is considered first. If distances are identical, the worker's ID and then the bike's ID are used as tiebreakers. - Inside the
matchWorkersAndBikesmethod, lists of distances are first sorted using the built-inComparatorfor pairs before being added to priority queues.
- A priority queue (
Assignment Logic:
- For each worker, an initial bike is assigned through the
assignNextBikemethod, which also handles subsequent bike assignments if the current bike is already taken. - When a bike assignment is to be made, the algorithm checks if the current worker already has a bike assigned and if the current bike has not yet been assigned to another worker. If both conditions are true, the assignment is confirmed.
- For each worker, an initial bike is assigned through the
Returning Results:
- The final assignments are stored in an array
workersAssignmentwhich is initialized with-1(indicating no initial bike assignment), and is updated as valid assignments are made through the iterating process of the priority queue. The method finally returns this array containing the assignments for all workers.
- The final assignments are stored in an array
This implementation effectively uses greedy techniques along with data sorting and priority queuing to ensure the most optimal bike is assigned to each worker based on distance criteria.
class Solution:
def matchWorkersWithBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
# calculates Manhattan distance between worker and bike
def calculate_distance(worker_point, bike_point):
return abs(worker_point[0] - bike_point[0]) + abs(worker_point[1] - bike_point[1])
all_combs = []
min_heap = []
for i, worker_position in enumerate(workers):
tmp_list = []
for j, bike_position in enumerate(bikes):
dist = calculate_distance(worker_position, bike_position)
tmp_list.append((dist, i, j))
# Sort in descending order to later pop the smallest distances
tmp_list.sort(reverse=True)
# Push the closest available bike to the heap
heapq.heappush(min_heap, tmp_list.pop())
# Store remaining pairs
all_combs.append(tmp_list)
bike_taken = [False] * len(bikes)
result = [-1] * len(workers)
while min_heap:
dist, worker_id, bike_id = heapq.heappop(min_heap)
if not bike_taken[bike_id]:
bike_taken[bike_id] = True
result[worker_id] = bike_id
else:
heapq.heappush(min_heap, all_combs[worker_id].pop())
return result
The given Python3 code snippet defines a method to match workers with bikes based on the minimum Manhattan distance between them. The class Solution contains a method matchWorkersWithBikes, which takes two sets of points — workers and bikes — represented as a list of lists containing coordinates.
- The function
calculate_distancecomputes the Manhattan distance between a worker and a bike. - The method iterates through each worker, and for each worker, it computes the distance to each bike, pairing the worker ID, bike ID, and distance into tuples.
- These tuples for each worker are sorted based on distance in descending order and stored into
min_heap, ensuring that the smallest distance can be retrieved efficiently. - The bike assignment is managed such that once a bike is assigned to a worker, it cannot be assigned again, which is tracked by the
bike_takenlist. - The process repeats by popping tuples from
min_heapand assigning them to workers if the bike has not yet been taken; if the bike is taken, the next best tuple for that worker is pushed onto the heap. - The assignment process continues until all valid tuples are exhausted or all workers have been assigned bikes.
This method guarantees that each worker is paired with the nearest available bike efficiently using the concept of priority queues (heap). The solution prioritizes minimizing the total distance between assigned worker-bike pairs.
No comments yet.