在由 2D 网格表示的校园里有 n 位工人(worker)和 m 辆自行车(bike),n <= m。所有工人和自行车的位置都用网格上的 2D 坐标表示。
我们需要为每位工人分配一辆自行车。在所有可用的自行车和工人中,我们选取彼此之间曼哈顿距离最短的工人自行车对 (worker, bike) ,并将其中的自行车分配給工人。如果有多个 (worker, bike) 对之间的曼哈顿距离相同,那么我们选择工人索引最小的那对。类似地,如果有多种不同的分配方法,则选择自行车索引最小的一对。不断重复这一过程,直到所有工人都分配到自行车为止。
给定两点 p1 和 p2 之间的曼哈顿距离为 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。
返回长度为 n 的向量 ans,其中 a[i] 是第 i 位工人分配到的自行车的索引(从 0 开始)。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/campus-bikes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
class Solution {
public int[] assignBikes(int[][] workers, int[][] bikes) {
int n = workers.length; // n <= m
int m = bikes.length;
PriorityQueue<Pair> heap = new PriorityQueue<>((a, b) -> {
if (a.distance != b.distance) return a.distance - b.distance;
if (a.worker != b.worker) return a.worker - b.worker;
return a.bike - b.bike;
});
int[] assignment = new int[n];
Set<Integer> workerPool = new HashSet<>();
Set<Integer> bikePool = new HashSet<>();
for (int i = 0; i < n; i++) workerPool.add(i);
for (int i = 0; i < m; i++) bikePool.add(i);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
Pair p = new Pair(i, j, workers[i], bikes[j]);
heap.offer(p);
}
}
while (workerPool.size() > 0) {
Pair p = heap.poll();
if (workerPool.contains(p.worker) && bikePool.contains(p.bike)) {
assignment[p.worker] = p.bike;
workerPool.remove(p.worker);
bikePool.remove(p.bike);
}
}
return assignment;
}
private int manhattanDistance(int[] worker, int[] bike) {
return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
}
class Pair {
int worker;
int bike;
int distance;
Pair(int worker, int bike, int[] wc, int[] bc) {
this.worker = worker;
this.bike = bike;
distance = manhattanDistance(wc, bc);
}
}
}