# 1057. Campus Bikes     • Time: $O(nm)$
• Space: $O(nm)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector assignBikes(vector>& workers, vector>& bikes) { const int n = workers.size(); const int m = bikes.size(); vector ans(n, -1); vector usedBikes(m); // buckets[k] := (i, j), where k = dist(workers[i], bikes[j]) vector>> buckets(2001); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) buckets[dist(workers[i], bikes[j])].emplace_back(i, j); for (int k = 0; k < 2001; ++k) for (const auto& [i, j] : buckets[k]) if (ans[i] == -1 && !usedBikes[j]) { ans[i] = j; usedBikes[j] = true; } return ans; } private: int dist(const vector& p1, const vector& p2) { return abs(p1 - p2) + abs(p1 - p2); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public int[] assignBikes(int[][] workers, int[][] bikes) { final int n = workers.length; final int m = bikes.length; int[] ans = new int[n]; boolean[] usedBikes = new boolean[m]; // buckets[k] := (i, j), where k = dist(workers[i], bikes[j]) List>[] buckets = new List; for (int i = 0; i < 2001; ++i) buckets[i] = new ArrayList<>(); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) buckets[dist(workers[i], bikes[j])].add(new Pair<>(i, j)); Arrays.fill(ans, -1); for (int k = 0; k < 2001; ++k) for (Pair pair : buckets[k]) { final int i = pair.getKey(); final int j = pair.getValue(); if (ans[i] == -1 && !usedBikes[j]) { ans[i] = j; usedBikes[j] = true; } } return ans; } private int dist(int[] p1, int[] p2) { return Math.abs(p1 - p2) + Math.abs(p1 - p2); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]: ans = [-1] * len(workers) usedBikes = [False] * len(bikes) # buckets[k] := (i, j), where k = dist(workers[i], bikes[j]) buckets = [[] for _ in range(2001)] def dist(p1: List[int], p2: List[int]) -> int: return abs(p1 - p2) + abs(p1 - p2) for i, worker in enumerate(workers): for j, bike in enumerate(bikes): buckets[dist(worker, bike)].append((i, j)) for k in range(2001): for i, j in buckets[k]: if ans[i] == -1 and not usedBikes[j]: ans[i] = j usedBikes[j] = True return ans