Campus bikes

Array Sorting Heap (Priority Queue)

59.1% acceptance

Mar 31, 2026

1002

198

On a campus represented on the X-Y plane, there are n workers and m bikes, with n <= m. You are given an array workers of length n where workers[i] = [xi, yi] is the position of the ith worker. You are also given an array bikes of length m where bikes[j] = [xj, yj] is the position of the jth bike. All the given positions are unique. Assign a bike to each worker. Among the available bikes and workers, we choose the (workeri, bikej) pair with the shortest Manhattan distance between each other and assign the bike to that worker. If there are multiple (workeri, bikej) 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 (0-indexed) of the bike that the ith 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|.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn assign_bikes(workers: Vec<Vec<i32>>, bikes: Vec<Vec<i32>>) -> Vec<i32> {
    let n = workers.len();
    let m = bikes.len();
    // Max Manhattan distance is (999-0)+(999-0) = 1998
    let mut buckets: Vec<Vec<(usize, usize)>> = vec![vec![]; 2000];
    for (wi, w) in workers.iter().enumerate() {
      for (bi, b) in bikes.iter().enumerate() {
        let dist = ((w[0] - b[0]).abs() + (w[1] - b[1]).abs()) as usize;
        buckets[dist].push((wi, bi));
      }
    }
    let mut result = vec![-1i32; n];
    let mut worker_taken = vec![false; n];
    let mut bike_taken = vec![false; m];
    let mut assigned = 0;
    'outer: for bucket in &buckets {
      for &(wi, bi) in bucket {
        if !worker_taken[wi] && !bike_taken[bi] {
          result[wi] = bi as i32;
          worker_taken[wi] = true;
          bike_taken[bi] = true;
          assigned += 1;
          if assigned == n { break 'outer; }
        }
      }
    }
    result
  }
}