Skip to content

Commit f6eb567

Browse files
fishercoder1534fishercoder1534
committed
add 1066
1 parent 91c918e commit f6eb567

File tree

3 files changed

+146
-0
lines changed

3 files changed

+146
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,7 @@ _If you like this project, please leave me a star._ ★
105105
|1079|[Letter Tile Possibilities](https://leetcode.com/problems/letter-tile-possibilities/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1079.java)| |Medium||
106106
|1078|[Occurrences After Bigram](https://leetcode.com/problems/occurrences-after-bigram/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1078.java) | |Easy||
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||
108+
|1066|[Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1066.java) | |Medium|Backtracking, DP|
108109
|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||
109110
|1062|[Longest Repeating Substring](https://leetcode.com/problems/longest-repeating-substring/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1062.java) | |Medium||
110111
|1057|[Campus Bikes](https://leetcode.com/problems/campus-bikes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1057.java) | |Medium||Greedy, Sort

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

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 1066. Campus Bikes II
5+
*
6+
* 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.
7+
* We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.
8+
* The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
9+
* Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.
10+
*
11+
* Example 1:
12+
* Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
13+
* Output: 6
14+
* Explanation:
15+
* We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.
16+
*
17+
* Example 2:
18+
* Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
19+
* Output: 4
20+
* Explanation:
21+
* We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1.
22+
* Both assignments lead to sum of the Manhattan distances as 4.
23+
*
24+
* Note:
25+
* 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
26+
* All worker and bike locations are distinct.
27+
* 1 <= workers.length <= bikes.length <= 10
28+
* */
29+
public class _1066 {
30+
public static class Solution1 {
31+
int minSum = Integer.MAX_VALUE;
32+
33+
public int assignBikes(int[][] workers, int[][] bikes) {
34+
backtracking(workers, bikes, 0, new boolean[bikes.length], 0);
35+
return minSum;
36+
}
37+
38+
private void backtracking(int[][] workers, int[][] bikes, int workersIndex, boolean[] bikesAssigned, int currentSum) {
39+
if (workersIndex >= workers.length) {
40+
minSum = Math.min(minSum, currentSum);
41+
return;
42+
}
43+
if (currentSum > minSum) {
44+
return;
45+
}
46+
for (int j = 0; j < bikes.length; j++) {
47+
if (!bikesAssigned[j]) {
48+
bikesAssigned[j] = true;
49+
backtracking(workers, bikes, workersIndex + 1, bikesAssigned, currentSum + dist(workers[workersIndex], bikes[j]));
50+
bikesAssigned[j] = false;
51+
}
52+
}
53+
}
54+
55+
private int dist(int[] worker, int[] bike) {
56+
return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
57+
}
58+
}
59+
}

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

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1066;
4+
import org.junit.Test;
5+
6+
import static org.junit.Assert.assertEquals;
7+
8+
public class _1066Test {
9+
private static _1066.Solution1 solution1;
10+
private static int[][] workers;
11+
private static int[][] bikes;
12+
13+
@Test
14+
public void test1() {
15+
solution1 = new _1066.Solution1();
16+
workers = new int[][]{
17+
{0, 0},
18+
{2, 1},
19+
};
20+
bikes = new int[][]{
21+
{1, 2},
22+
{3, 3},
23+
};
24+
assertEquals(6, solution1.assignBikes(workers, bikes));
25+
}
26+
27+
@Test
28+
public void test2() {
29+
solution1 = new _1066.Solution1();
30+
workers = new int[][]{
31+
{0, 0},
32+
{1, 1},
33+
{2, 0},
34+
};
35+
bikes = new int[][]{
36+
{1, 0},
37+
{2, 2},
38+
{2, 1},
39+
};
40+
assertEquals(4, solution1.assignBikes(workers, bikes));
41+
}
42+
43+
@Test
44+
public void test3() {
45+
solution1 = new _1066.Solution1();
46+
workers = new int[][]{
47+
{0, 0},
48+
{1, 0},
49+
{2, 0},
50+
{3, 0},
51+
{4, 0},
52+
{5, 0},
53+
};
54+
bikes = new int[][]{
55+
{0, 999},
56+
{1, 999},
57+
{2, 999},
58+
{3, 999},
59+
{4, 999},
60+
{5, 999},
61+
{6, 999},
62+
{7, 999},
63+
};
64+
assertEquals(5994, solution1.assignBikes(workers, bikes));
65+
}
66+
67+
@Test
68+
public void test4() {
69+
solution1 = new _1066.Solution1();
70+
workers = new int[][]{
71+
{815, 60},
72+
{638, 626},
73+
{6, 44},
74+
{103, 90},
75+
{591, 880},
76+
};
77+
bikes = new int[][]{
78+
{709, 161},
79+
{341, 339},
80+
{755, 955},
81+
{172, 27},
82+
{433, 489},
83+
};
84+
assertEquals(1458, solution1.assignBikes(workers, bikes));
85+
}
86+
}

0 commit comments

Comments
 (0)