source: https://leetcode.com/problems/campus-bikes/description/
Campus Bikes
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 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.
Approach 1 (Time Limit Exceeded)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
class Solution { TLE public int[] assignBikes(int[][] workers, int[][] bikes) { Map<String, Integer> bikeMap = new HashMap<>(); for(int i=0;i<bikes.length;i++){ bikeMap.put(bikes[i][0]+":"+bikes[i][1], i); } Queue<Worker> next = new LinkedList<>(); HashSet<Integer> assigned = new HashSet<>(); HashSet<String> visited = new HashSet<>(); for(int i=0; i<workers.length; i++){ next.offer(new Worker(workers[i][0], workers[i][1], i)); visited.add(workers[i][0] + ":" + workers[i][1] + ":" + i); } int[] assignments = new int[workers.length]; int[] x = {-1, 0, 0, 1}; int[] y = {0, -1, 1, 0}; while(!next.isEmpty()){ int len = next.size(); for(int i=0;i<len;i++){ Worker w = next.poll(); if(assigned.contains(w.index)){ continue; } String key = w.x+":"+w.y; if(bikeMap.containsKey(key)){ assignments[w.index] = bikeMap.remove(key); assigned.add(w.index); } if(assigned.size()==workers.length){ return assignments; } for(int j=0;j<x.length;j++){ int px = x[j] + w.x; int py = y[j] + w.y; if(isValid(px, py, w.index, visited)){ next.offer(new Worker(px, py, w.index)); visited.add(px + ":"+ py + ":"+ w.index); } } } } return null; } private boolean isValid(int px, int py, int pi, HashSet<String> visited){ return px >=0 && px < 1000 && py >= 0 && py < 1000 && !visited.contains(px + ":" + py + ":" + pi); } static class Worker { int x; int y; int index; public Worker(int x, int y, int index){ this.x = x; this.y = y; this.index = index; } } } |
Approach 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
class Solution { public int[] assignBikes(int[][] workers, int[][] bikes) { Map<Integer, PriorityQueue<Bike>> map = initialize(workers, bikes); HashSet<Integer> workerAssigned = new HashSet<>(); HashSet<Integer> bikeAssigned = new HashSet<>(); int[] assigned = new int[workers.length]; for(int i=0;i<workers.length;i++){ int minDist = Integer.MAX_VALUE; int minIndex = 1000; int bike = -1; for(Map.Entry<Integer, PriorityQueue<Bike>> entry: map.entrySet()){ int wi = entry.getKey(); PriorityQueue<Bike> p = entry.getValue(); while(!p.isEmpty() && bikeAssigned.contains(p.peek().index)){ p.poll(); } if(!p.isEmpty()){ Bike b = p.peek(); if(b.dist < minDist || (b.dist==minDist && wi < minIndex)){ minDist = b.dist; minIndex = wi; bike = b.index; } } } map.remove(minIndex); assigned[minIndex] = bike; workerAssigned.add(minIndex); bikeAssigned.add(bike); if(workerAssigned.size()==workers.length){ return assigned; } } return null; } private Map<Integer, PriorityQueue<Bike>> initialize(int[][] workers, int[][] bikes){ Map<Integer, PriorityQueue<Bike>> map = new HashMap<>(); for(int i=0; i<workers.length;i++){ int wx = workers[i][0]; int wy = workers[i][1]; PriorityQueue<Bike> p = new PriorityQueue<>(new Comparator<Bike>(){ public int compare(Bike a, Bike b){ int res = a.dist - b.dist; if(res==0){ res = a.index - b.index; } return res; } }); for(int j=0;j<bikes.length;j++){ int bx = bikes[j][0]; int by = bikes[j][1]; p.offer(new Bike(wx, wy, bx, by, j)); } map.put(i, p); } return map; } static class Bike { int x; int y; int index; int dist; public Bike (int wx, int wy, int x, int y, int index){ this.x = x; this.y = y; this.index = index; this.dist = distance(wx, wy, x, y); } } private static int distance(int wx, int wy, int bx, int by){ return Math.abs(wx- bx) + Math.abs(wy-by); } } |