11package com .fishercoder .solutions ;
22
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- * */
293public class _1066 {
304public static class Solution1 {
315int minSum =Integer .MAX_VALUE ;
@@ -44,7 +18,7 @@ private void backtracking(int[][] workers, int[][] bikes, int workersIndex, bool
4418if (currentSum >minSum ) {
4519return ;
4620 }
47-
21+
4822for (int j =0 ;j <bikes .length ;j ++) {
4923if (!bikesAssigned [j ]) {
5024bikesAssigned [j ] =true ;