题目描述
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.
样例
Please see the original link.
算法1
Java 代码
class Solution {
public int[] assignBikes(int[][] workers, int[][] bikes) {
int N = workers.length, M = bikes.length;
boolean[] used = new boolean[M];
List<Pair>[] graph = new List[N];
for(int i=0; i<N; i++) graph[i] = new ArrayList<>();
for(int i=0; i<N; i++) for(int j=0; j<M; j++) {
int[] w = workers[i], b = bikes[j];
int dist = Math.abs(w[0]-b[0]) + Math.abs(w[1]-b[1]);
graph[i].add(new Pair(dist, i, j, -1));
}
for(int i=0; i<N; i++) {
Collections.sort(graph[i]);
List<Pair> list = graph[i];
for(int j=0; j<list.size(); j++) list.get(j).idx = j;
}
PriorityQueue<Pair> heap = new PriorityQueue<>();
for(int i=0; i<N; i++) {
heap.add(graph[i].get(0));
}
int[] ret = new int[N];
Arrays.fill(ret, -1);
int count = N;
while(count > 0) {
Pair p = heap.poll();
if (used[p.bike]) {
int idx = p.idx+1;
while(used[graph[p.worker].get(idx).bike]) idx++;
p = graph[p.worker].get(idx);
heap.add(p);
continue;
}
ret[p.worker] = p.bike;
used[p.bike] = true;
count--;
}
return ret;
}
public class Pair implements Comparable<Pair> {
int dist, worker, bike, idx;
public Pair(int a, int b, int c, int d) {
dist = a;
worker = b;
bike = c;
idx = d;
}
@Override
public int compareTo(Pair p) {
if (this.dist != p.dist) return this.dist - p.dist;
if (this.worker != p.worker) return this.worker - p.worker;
return this.bike - p.bike;
}
}
}