On a campus represented on the X-Y plane, there are n workers and m bikes, with n <= m. You are given an array workers of length n where workers[i] = [xi, yi] is the position of the ith worker. You are also given an array bikes of length m where bikes[j] = [xj, yj] is the position of the jth bike. All the given positions are unique. Assign a bike to each worker. Among the available bikes and workers, we choose the (workeri, bikej) pair with the shortest Manhattan distance between each other and assign the bike to that worker. If there are multiple (workeri, bikej) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index. If there are multiple ways to do that, we choose the pair with the smallest bike index. Repeat this process until there are no available workers. Return an array answer of length n, where answer[i] is the index (0-indexed) of the bike that the ith worker is assigned to. The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
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.
- code sorting
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
def find_distance(worker_loc, bike_loc):
return abs(worker_loc[0] - bike_loc[0]) + abs(worker_loc[1] - bike_loc[1])
# Calculate the distance between each worker and bike.
all_triplets = []
for worker, worker_loc in enumerate(workers):
for bike, bike_loc in enumerate(bikes):
distance = find_distance(worker_loc, bike_loc)
all_triplets.append((distance, worker, bike))
# Sort the triplets. By default, sorting will prioritize the
# tuple's first value, then second value, and finally the third value
all_triplets.sort()
# Initialize all values to False, to signify no bikes have been taken
bike_status = [False] * len(bikes)
# Initialize all values to -1, to signify no worker has a bike
worker_status = [-1] * len(workers)
# Keep track of how many worker-bike pairs have been made
pair_count = 0
for distance, worker, bike in all_triplets:
# If both worker and bike are free, assign the bike to
# the worker and mark the bike as taken
if worker_status[worker] == -1 and not bike_status[bike]:
bike_status[bike] = True
worker_status[worker] = bike
pair_count += 1
# If all the workers have the bike assigned, we can stop
if pair_count == len(workers):
return worker_status
return worker_status
- code
class Solution {
// List of pairs (distance, bike index) for each bike corresponding to worker
List<List<Pair<Integer, Integer>>> workerToBikeList = new ArrayList<>();
// Stores the closest bike index, corresponding to the worker index
int closestBikeIndex[] = new int[1001];
// Class to store (worker, bike, distance)
class WorkerBikePair {
int workerIndex;
int bikeIndex;
int distance;
// Constructor to initialize the member variables
WorkerBikePair(int workerIndex, int bikeIndex, int distance) {
this.workerIndex = workerIndex;
this.bikeIndex = bikeIndex;
this.distance = distance;
}
}
// Custom comparator for comparing WorkerBikePair in priority queue
Comparator<WorkerBikePair> WorkerBikePairComparator
= new Comparator<WorkerBikePair>() {
@Override
public int compare(WorkerBikePair a, WorkerBikePair b) {
if (a.distance != b.distance) {
// Prioritize the one having smaller distance
return a.distance - b.distance;
} else if (a.workerIndex != b.workerIndex) {
// Prioritize according to the worker index
return a.workerIndex - b.workerIndex;
} else {
// Prioritize according to the bike index
return a.bikeIndex - b.bikeIndex;
}
}
};
// Function to return the Manhattan distance
int findDistance(int[] worker, int[] bike) {
return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
}
// Add the closest bike for the worker to the priority queue,
// And update the closest bike index
void addClosestBikeToPq(PriorityQueue<WorkerBikePair> pq, int worker) {
Pair<Integer, Integer> closestBike = workerToBikeList.get(worker)
.get(closestBikeIndex[worker]);
closestBikeIndex[worker]++;
WorkerBikePair workerBikePair
= new WorkerBikePair(worker, closestBike.getValue(), closestBike.getKey());
pq.add(workerBikePair);
}
public int[] assignBikes(int[][] workers, int[][] bikes) {
PriorityQueue<WorkerBikePair> pq = new PriorityQueue<>(
(WorkerBikePair a, WorkerBikePair b) -> a.distance == b.distance ? (a.workerIndex == b.workerIndex ? a.bikeIndex - b.bikeIndex : a.workerIndex - b.workerIndex ) : a.distance - b.distance
);
// Add all the bikes along with their distances from the worker
for (int worker = 0; worker < workers.length; worker++) {
List<Pair<Integer, Integer>> bikeList = new ArrayList<>();
for (int bike = 0; bike < bikes.length; bike++) {
int distance = findDistance(workers[worker], bikes[bike]);
bikeList.add(new Pair(distance, bike));
}
Collections.sort(bikeList, Comparator.comparing(Pair::getKey));
// Store all the bike options for the current worker in workerToBikeList
workerToBikeList.add(bikeList);
// First bike is the closest bike for each worker
closestBikeIndex[worker] = 0;
// For each worker, add their closest bike to the priority queue
addClosestBikeToPq(pq, worker);
}
// Initialize all values to false, to signify no bikes have been taken
boolean bikeStatus[] = new boolean[bikes.length];
// Initialize all index to -1, to mark all the workers available
int workerStatus[] = new int[workers.length];
Arrays.fill(workerStatus, -1);
// Until all workers have not been assigned a bike
while (!pq.isEmpty()) {
// Pop the pair with smallest distance
WorkerBikePair workerBikePair = pq.remove();
int worker = workerBikePair.workerIndex;
int bike = workerBikePair.bikeIndex;
if (workerStatus[worker] == -1 && !bikeStatus[bike]) {
// If both worker and bike are free, assign them to each other
bikeStatus[bike] = true;
workerStatus[worker] = bike;
} else {
// Add the next closest bike for the current worker
addClosestBikeToPq(pq, worker);
}
}
return workerStatus;
}
}