Welcome to Subscribe On Youtube
1057. Campus Bikes
Description
On a campus represented on the XY plane, there are n
workers and m
bikes, with n <= m
.
You are given an array workers
of length n
where workers[i] = [x_{i}, y_{i}]
is the position of the i^{th}
worker. You are also given an array bikes
of length m
where bikes[j] = [x_{j}, y_{j}]
is the position of the j^{th}
bike. All the given positions are unique.
Assign a bike to each worker. Among the available bikes and workers, we choose the (worker_{i}, bike_{j})
pair with the shortest Manhattan distance between each other and assign the bike to that worker.
If there are multiple (worker_{i}, bike_{j})
pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index. If there are multiple ways to do that, we choose the pair with the smallest bike index. Repeat this process until there are no available workers.
Return an array answer
of length n
, where answer[i]
is the index (0indexed) of the bike that the i^{th}
worker is assigned to.
The Manhattan distance between two points p1
and p2
is Manhattan(p1, p2) = p1.x  p2.x + p1.y  p2.y
.
Example 1:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: [1,0] Explanation: Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].
Example 2:
Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] Output: [0,2,1] Explanation: Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].
Constraints:
n == workers.length
m == bikes.length
1 <= n <= m <= 1000
workers[i].length == bikes[j].length == 2
0 <= x_{i}, y_{i} < 1000
0 <= x_{j}, y_{j} < 1000
 All worker and bike locations are unique.
Solutions

class Solution { public int[] assignBikes(int[][] workers, int[][] bikes) { int n = workers.length, m = bikes.length; int[][] arr = new int[m * n][3]; for (int i = 0, k = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int dist = Math.abs(workers[i][0]  bikes[j][0]) + Math.abs(workers[i][1]  bikes[j][1]); arr[k++] = new int[] {dist, i, j}; } } Arrays.sort(arr, (a, b) > { if (a[0] != b[0]) { return a[0]  b[0]; } if (a[1] != b[1]) { return a[1]  b[1]; } return a[2]  b[2]; }); boolean[] vis1 = new boolean[n]; boolean[] vis2 = new boolean[m]; int[] ans = new int[n]; for (var e : arr) { int i = e[1], j = e[2]; if (!vis1[i] && !vis2[j]) { vis1[i] = true; vis2[j] = true; ans[i] = j; } } return ans; } }

class Solution { public: vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) { int n = workers.size(), m = bikes.size(); vector<tuple<int, int, int>> arr(n * m); for (int i = 0, k = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int dist = abs(workers[i][0]  bikes[j][0]) + abs(workers[i][1]  bikes[j][1]); arr[k++] = {dist, i, j}; } } sort(arr.begin(), arr.end()); vector<bool> vis1(n), vis2(m); vector<int> ans(n); for (auto& [_, i, j] : arr) { if (!vis1[i] && !vis2[j]) { vis1[i] = true; vis2[j] = true; ans[i] = j; } } return ans; } };

class Solution: def assignBikes( self, workers: List[List[int]], bikes: List[List[int]] ) > List[int]: n, m = len(workers), len(bikes) arr = [] for i, j in product(range(n), range(m)): dist = abs(workers[i][0]  bikes[j][0]) + abs(workers[i][1]  bikes[j][1]) arr.append((dist, i, j)) arr.sort() vis1 = [False] * n vis2 = [False] * m ans = [0] * n for _, i, j in arr: if not vis1[i] and not vis2[j]: vis1[i] = vis2[j] = True ans[i] = j return ans

func assignBikes(workers [][]int, bikes [][]int) []int { n, m := len(workers), len(bikes) type tuple struct{ d, i, j int } arr := make([]tuple, n*m) for i, k := 0, 0; i < n; i++ { for j := 0; j < m; j++ { d := abs(workers[i][0]bikes[j][0]) + abs(workers[i][1]bikes[j][1]) arr[k] = tuple{d, i, j} k++ } } sort.Slice(arr, func(i, j int) bool { if arr[i].d != arr[j].d { return arr[i].d < arr[j].d } if arr[i].i != arr[j].i { return arr[i].i < arr[j].i } return arr[i].j < arr[j].j }) vis1, vis2 := make([]bool, n), make([]bool, m) ans := make([]int, n) for _, e := range arr { i, j := e.i, e.j if !vis1[i] && !vis2[j] { vis1[i], vis2[j] = true, true ans[i] = j } } return ans } func abs(x int) int { if x < 0 { return x } return x }