Update Campus Bikes.java

varunu28 · web-flow · commit 220c742237ac · 2023-11-01T12:40:35.000+05:30
diff --git a/Medium/Campus Bikes.java b/Medium/Campus Bikes.java
@@ -1,46 +1,39 @@
 class Solution {
-  public int[] assignBikes(int[][] workers, int[][] bikes) {
-    PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>(){
-      public int compare(Node n1, Node n2) {
-        int c = n1.dist - n2.dist;
-        if (c != 0) {
-          return c;
+    public int[] assignBikes(int[][] workers, int[][] bikes) {
+        int workerCount = workers.length;
+        int bikeCount = bikes.length;
+        PriorityQueue<WorkerBikePair> priorityQueue = new PriorityQueue<>();
+        for (int i = 0; i < workerCount; i++) {
+            for (int j = 0; j < bikeCount; j++) {
+                priorityQueue.add(new WorkerBikePair(manhattanDistance(workers[i], bikes[j]), i, j));
+            }
         }
-        c = n1.workIdx - n2.workIdx;
-        return c != 0 ? c : n1.cycleIdx - n2.cycleIdx;
-      }
-    });
-    for (int i = 0; i < workers.length; i++) {
-      for (int j = 0; j < bikes.length; j++) {
-        pq.add(new Node(getDist(workers[i], bikes[j]), i, j));
-      }
+        Set<Integer> bikeDone = new HashSet<>();
+        int[] result = new int[workerCount];
+        Arrays.fill(result, Integer.MIN_VALUE);
+        while (!priorityQueue.isEmpty()) {
+            WorkerBikePair removed = priorityQueue.remove();
+            if (result[removed.workerIdx] == Integer.MIN_VALUE && !bikeDone.contains(removed.bikeIdx)) {
+                result[removed.workerIdx] = removed.bikeIdx;
+                bikeDone.add(removed.bikeIdx);
+            }
+        }
+        return result;
     }
-    int[] ans = new int[workers.length];
-    boolean[] bikesTaken = new boolean[bikes.length];
-    Arrays.fill(ans, Integer.MIN_VALUE);
-    while (!pq.isEmpty()) {
-      Node node = pq.remove();
-      if (ans[node.workIdx] == Integer.MIN_VALUE && !bikesTaken[node.cycleIdx]) {
-        ans[node.workIdx] = node.cycleIdx;
-        bikesTaken[node.cycleIdx] = true;
-      }
+
+    private record WorkerBikePair(int manhattanDistance, int workerIdx, int bikeIdx) implements Comparable<WorkerBikePair> {
+        @Override
+        public int compareTo(WorkerBikePair o) {
+            int c = manhattanDistance - o.manhattanDistance;
+            if (c != 0) {
+                return c;
+            }
+            c = workerIdx - o.workerIdx;
+            return c != 0 ? c : bikeIdx - o.bikeIdx;
+        }
     }
-    return ans;
-  }
-  
-  private int getDist(int[] p1, int[] p2) {
-    return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
-  }
-}
 
-class Node {
-  int dist;
-  int workIdx;
-  int cycleIdx;
-  
-  public Node(int dist, int workIdx, int cycleIdx) {
-    this.dist = dist;
-    this.workIdx = workIdx;
-    this.cycleIdx = cycleIdx;
-  }
+    private static int manhattanDistance(int[] p1, int[] p2) {
+        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
+    }
 }
