求谷歌高频题1057.Campus Bikes的答案

非利口会员，求大佬share一下高票答案和解释

题目细节很多，这题是简化的。

差别在于如果有另外一对人跟同一辆车车等同距离出现时， 你怎么做。

比如人[0, 0], [2,0], 车[1,0], [100,0]

本质是一个二分图匹配，标准解法是最大流。

n数字不大时可以选择tsp，数位dp。

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


直接贪心法一个一个算就好了

高票答案

    We are able to solve this question using a greedy approach.

    initiate a priority queue of bike and worker pairs. The heap order should be Distance ASC, WorkerIndex ASC, Bike ASC
    Loop through all workers and bikes, calculate their distance, and then throw it to the queue.
    Initiate a set to keep track of the bikes that have been assigned.
    initiate a result array and fill it with -1. (unassigned)
    poll every possible pair from the priority queue and check if the person already got his bike or the bike has been assigned.
    early exist on every people got their bike.

This is my first post on LeetCode.
Let me know if you got any questions :D

   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;
    }

xiangzhongdi 发表于 2019-7-14 08:53
On a campus represented as a 2D grid, there are N workers and M bikes, with N

求贴一个可以ac的答案，java的最好

xiangzhongdi 发表于 2019-7-14 08:58
高票答案

    We are able to solve this question using a greedy approach.

heap order slower than priority queue

337845818 发表于 2019-9-28 08:29
题目细节很多，这题是简化的。

差别在于如果有另外一对人跟同一辆车车等同距离出现时， 你怎么做。

感谢大神

补充一下，具体来讲是用KM算法，并把顶标值与边值设为负的，这样就可以得到最小流

MD LeetCode的题都好嗨难啊，什么时候才是个头啊TMD