_1066.java

packagecom.fishercoder.solutions.secondthousand;

publicclass_1066 {
publicstaticclassSolution1 {
intminSum = Integer.MAX_VALUE;

publicintassignBikes(int[][] workers, int[][] bikes) {
backtracking(workers, bikes, 0, newboolean[bikes.length], 0);
returnminSum;
 }

privatevoidbacktracking(
int[][] workers,
int[][] bikes,
intworkersIndex,
boolean[] bikesAssigned,
intcurrentSum) {
if (workersIndex >= workers.length) {
minSum = Math.min(minSum, currentSum);
return;
 }

if (currentSum > minSum) {
return;
 }

for (intj = 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;
 }
 }
 }

privateintdist(int[] worker, int[] bike) {
returnMath.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
 }
 }
}