Skip to content

Commit d25eb68

Browse files
fishercoder1534fishercoder1534
committed
add 1057
1 parent 0a00e64 commit d25eb68

File tree

3 files changed

+125
-0
lines changed

3 files changed

+125
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,7 @@ _If you like this project, please leave me a star._ ★
107107
|1071|[Greatest Common Divisor of Strings](https://leetcode.com/problems/greatest-common-divisor-of-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1071.java) | |Easy||
108108
|1065|[Index Pairs of a String](https://leetcode.com/problems/index-pairs-of-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1065.java) | |Medium||
109109
|1062|[Longest Repeating Substring](https://leetcode.com/problems/longest-repeating-substring/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1062.java) | |Medium||
110+
|1057|[Campus Bikes](https://leetcode.com/problems/campus-bikes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1057.java) | |Medium||Greedy, Sort
110111
|1056|[Confusing Number](https://leetcode.com/problems/confusing-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1056.java) | |Easy||
111112
|1055|[Fixed Point](https://leetcode.com/problems/fixed-point/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1055.java) | |Easy||
112113
|1051|[Height Checker](https://leetcode.com/problems/height-checker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1051.java) | |Easy||

‎src/main/java/com/fishercoder/solutions/_1057.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.PriorityQueue;
4+
import java.util.TreeMap;
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+
public class _1057 {
38+
public static class Solution1 {
39+
public int[] assignBikes(int[][] workers, int[][] bikes) {
40+
int w = workers.length;
41+
int b = bikes.length;
42+
TreeMap<Integer, PriorityQueue<int[]>> treeMap = new TreeMap<>();
43+
for (int i = 0; i < w; i++) {
44+
for (int j = 0; j < b; j++) {
45+
int distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
46+
if (!treeMap.containsKey(distance)) {
47+
treeMap.put(distance, new PriorityQueue<>((x, y) -> x[0] == y[0] ? x[1] - y[1] : x[0] - y[0]));
48+
}
49+
treeMap.get(distance).add(new int[]{i, j});
50+
}
51+
}
52+
int[] ans = new int[w];
53+
for (int i = 0; i < w; i++) {
54+
ans[i] = -1;
55+
}
56+
boolean[] assigned = new boolean[b];
57+
int workersHaveBikes = 0;
58+
for (int dist : treeMap.keySet()) {
59+
PriorityQueue<int[]> workerBikePairs = treeMap.get(dist);
60+
while (!workerBikePairs.isEmpty()) {
61+
int[] workerBikePair = workerBikePairs.poll();
62+
if (ans[workerBikePair[0]] == -1) {
63+
if (!assigned[workerBikePair[1]]) {
64+
assigned[workerBikePair[1]] = true;
65+
ans[workerBikePair[0]] = workerBikePair[1];
66+
workersHaveBikes++;
67+
}
68+
}
69+
}
70+
if (workersHaveBikes == w) {
71+
return ans;
72+
}
73+
}
74+
return ans;
75+
}
76+
}
77+
}

‎src/test/java/com/fishercoder/_1057Test.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1057;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertArrayEquals;
8+
9+
public class _1057Test {
10+
private static _1057.Solution1 solution1;
11+
private static int[][] workers;
12+
private static int[][] bikes;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _1057.Solution1();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
workers = new int[][]{
22+
{0, 0},
23+
{2, 1},
24+
};
25+
bikes = new int[][]{
26+
{1, 2},
27+
{3, 3},
28+
};
29+
assertArrayEquals(new int[]{1, 0}, solution1.assignBikes(workers, bikes));
30+
}
31+
32+
@Test
33+
public void test2() {
34+
workers = new int[][]{
35+
{0, 0},
36+
{1, 1},
37+
{2, 0},
38+
};
39+
bikes = new int[][]{
40+
{1, 0},
41+
{2, 2},
42+
{2, 1},
43+
};
44+
assertArrayEquals(new int[]{0, 2, 1}, solution1.assignBikes(workers, bikes));
45+
}
46+
47+
}

0 commit comments

Comments
 (0)