add 1066

fishercoder1534 · fishercoder1534 · commit f6eb56798ac7 · 2020-02-20T17:20:50.000-08:00
diff --git a/README.md b/README.md
@@ -105,6 +105,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1079|[Letter Tile Possibilities](https://leetcode.com/problems/letter-tile-possibilities/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1079.java)| |Medium||
 |1078|[Occurrences After Bigram](https://leetcode.com/problems/occurrences-after-bigram/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1078.java) | |Easy||
 |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||
+|1066|[Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1066.java) | |Medium|Backtracking, DP|
 |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||
 |1062|[Longest Repeating Substring](https://leetcode.com/problems/longest-repeating-substring/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1062.java) | |Medium||
 |1057|[Campus Bikes](https://leetcode.com/problems/campus-bikes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1057.java) | |Medium||Greedy, Sort
diff --git a/src/main/java/com/fishercoder/solutions/_1066.java b/src/main/java/com/fishercoder/solutions/_1066.java
@@ -0,0 +1,59 @@
+package com.fishercoder.solutions;
+
+/**
+ * 1066. Campus Bikes II
+ *
+ * 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.
+ * 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.
+ * The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
+ * Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.
+ *
+ * Example 1:
+ * Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
+ * Output: 6
+ * Explanation:
+ * 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.
+ *
+ * Example 2:
+ * Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
+ * Output: 4
+ * Explanation:
+ * 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.
+ * Both assignments lead to sum of the Manhattan distances as 4.
+ *
+ * Note:
+ * 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
+ * All worker and bike locations are distinct.
+ * 1 <= workers.length <= bikes.length <= 10
+ * */
+public class _1066 {
+    public static class Solution1 {
+        int minSum = Integer.MAX_VALUE;
+
+        public int assignBikes(int[][] workers, int[][] bikes) {
+            backtracking(workers, bikes, 0, new boolean[bikes.length], 0);
+            return minSum;
+        }
+
+        private void backtracking(int[][] workers, int[][] bikes, int workersIndex, boolean[] bikesAssigned, int currentSum) {
+            if (workersIndex >= workers.length) {
+                minSum = Math.min(minSum, currentSum);
+                return;
+            }
+            if (currentSum > minSum) {
+                return;
+            }
+            for (int j = 0; j < bikes.length; j++) {
+                if (!bikesAssigned[j]) {
+                    bikesAssigned[j] = true;
+                    backtracking(workers, bikes, workersIndex + 1, bikesAssigned, currentSum + dist(workers[workersIndex], bikes[j]));
+                    bikesAssigned[j] = false;
+                }
+            }
+        }
+
+        private int dist(int[] worker, int[] bike) {
+            return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1066Test.java b/src/test/java/com/fishercoder/_1066Test.java
@@ -0,0 +1,86 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1066;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1066Test {
+    private static _1066.Solution1 solution1;
+    private static int[][] workers;
+    private static int[][] bikes;
+
+    @Test
+    public void test1() {
+        solution1 = new _1066.Solution1();
+        workers = new int[][]{
+                {0, 0},
+                {2, 1},
+        };
+        bikes = new int[][]{
+                {1, 2},
+                {3, 3},
+        };
+        assertEquals(6, solution1.assignBikes(workers, bikes));
+    }
+
+    @Test
+    public void test2() {
+        solution1 = new _1066.Solution1();
+        workers = new int[][]{
+                {0, 0},
+                {1, 1},
+                {2, 0},
+        };
+        bikes = new int[][]{
+                {1, 0},
+                {2, 2},
+                {2, 1},
+        };
+        assertEquals(4, solution1.assignBikes(workers, bikes));
+    }
+
+    @Test
+    public void test3() {
+        solution1 = new _1066.Solution1();
+        workers = new int[][]{
+                {0, 0},
+                {1, 0},
+                {2, 0},
+                {3, 0},
+                {4, 0},
+                {5, 0},
+        };
+        bikes = new int[][]{
+                {0, 999},
+                {1, 999},
+                {2, 999},
+                {3, 999},
+                {4, 999},
+                {5, 999},
+                {6, 999},
+                {7, 999},
+        };
+        assertEquals(5994, solution1.assignBikes(workers, bikes));
+    }
+
+    @Test
+    public void test4() {
+        solution1 = new _1066.Solution1();
+        workers = new int[][]{
+                {815, 60},
+                {638, 626},
+                {6, 44},
+                {103, 90},
+                {591, 880},
+        };
+        bikes = new int[][]{
+                {709, 161},
+                {341, 339},
+                {755, 955},
+                {172, 27},
+                {433, 489},
+        };
+        assertEquals(1458, solution1.assignBikes(workers, bikes));
+    }
+}
