|
3 | 3 | importjava.util.PriorityQueue; |
4 | 4 | importjava.util.TreeMap; |
5 | 5 |
|
6 | | -/** |
7 | | - * 1057. Campus Bikes |
8 | | - * |
9 | | - * 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. |
10 | | - * Our goal is to assign a bike to each worker. |
11 | | - * Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, |
12 | | - * and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, |
13 | | - * we choose the pair with the smallest worker index; if there are multiple ways to do that, |
14 | | - * we choose the pair with the smallest bike index). We repeat this process until there are no available workers. |
15 | | - * |
16 | | - * The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. |
17 | | - * 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. |
18 | | - * |
19 | | - * Example 1: |
20 | | - * Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] |
21 | | - * Output: [1,0] |
22 | | - * Explanation: |
23 | | - * Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0]. |
24 | | - * |
25 | | - * Example 2: |
26 | | - * Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] |
27 | | - * Output: [0,2,1] |
28 | | - * Explanation: |
29 | | - * Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, |
30 | | - * thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1]. |
31 | | - * |
32 | | - * Note: |
33 | | - * 0 <= workers[i][j], bikes[i][j] < 1000 |
34 | | - * All worker and bike locations are distinct. |
35 | | - * 1 <= workers.length <= bikes.length <= 1000 |
36 | | - * */ |
37 | 6 | publicclass_1057 { |
38 | 7 | publicstaticclassSolution1 { |
39 | 8 | publicint[]assignBikes(int[][]workers,int[][]bikes) { |
|