On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.
Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) 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). We repeat this process until there are no available workers.
The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Return a vector ans of length N, where ans[i] is the index (0-indexed) of the bike that the i-th worker is assigned to.
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].
Note:
0 <= workers[i][j], bikes[i][j] < 1000
All worker and bike locations are distinct.
1 <= workers.length <= bikes.length <= 1000
给一系列A的坐标和B的坐标，给每个a找曼哈顿距离最近的b，曼哈顿距离dist(a, b) = |a.x - a.x| + |b.y - b.y|。最短距离BFS或DP/greedy。这道题没有明显的格子，直接算出所有(a, b) pair的距离并从小到大排序，然后遍历所有距离并greedy的每次选dist最小来分配。由于距离有限（[0, 2000]），可以直接用bucket sort。
class Solution {
public:
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
vector<vector<int>> dists;
const int M = workers.size(), N = bikes.size();
vector<vector<vector<int>>> buckets(2001);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
const auto &w = workers[i], &b = bikes[j];
buckets[abs(w[0] - b[0]) + abs(w[1] - b[1])].push_back({i, j});
}
}
vector<int> res(M, -1);
vector<bool> assigned(N, false);
for (int i = 0; i <= 2000; ++i) {
for (const auto &d : buckets[i]) {
if (res[d[0]] != -1 || assigned[d[1]]) continue;
res[d[0]] = d[1];
assigned[d[1]] = true;
}
}
return res;
}
};
public int[] assignBikes(int[][] workers, int[][] bikes) {
int n = workers.length;
// order by Distance ASC, WorkerIndex ASC, BikeIndex ASC
PriorityQueue<int[]> q = new PriorityQueue<int[]>((a, b) -> {
int comp = Integer.compare(a[0], b[0]);
if (comp == 0) {
if (a[1] == b[1]) {
return Integer.compare(a[2], b[2]);
}
return Integer.compare(a[1], b[1]);
}
return comp;
});
// loop through every possible pairs of bikes and people,
// calculate their distance, and then throw it to the pq.
for (int i = 0; i < workers.length; i++) {
int[] worker = workers[i];
for (int j = 0; j < bikes.length; j++) {
int[] bike = bikes[j];
int dist = Math.abs(bike[0] - worker[0]) + Math.abs(bike[1] - worker[1]);
q.add(new int[]{dist, i, j});
}
}
// init the result array with state of 'unvisited'.
int[] res = new int[n];
Arrays.fill(res, -1);
// assign the bikes.
Set<Integer> bikeAssigned = new HashSet<>();
while (bikeAssigned.size() < n) {
int[] workerAndBikePair = q.poll();
if (res[workerAndBikePair[1]] == -1
&& !bikeAssigned.contains(workerAndBikePair[2])) {
res[workerAndBikePair[1]] = workerAndBikePair[2];
bikeAssigned.add(workerAndBikePair[2]);
}
}
return res;
}
