LeetCode Solutions

			

class Solution {
 public:
  vector<int> assignBikes(vector<vector<int>>& workers,
                          vector<vector<int>>& bikes) {
    const int n = workers.size();
    const int m = bikes.size();
    vector<int> ans(n, -1);
    vector<bool> usedBikes(m);
    // buckets[k] := (i, j), where k = dist(workers[i], bikes[j])
    vector<vector<pair<int, int>>> 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<int>& p1, const vector<int>& p2) {
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]);
  }
};

			

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<Pair<Integer, Integer>>[] buckets = new List[2001];

    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<Integer, Integer> 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[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
  }
}

			

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[0] - p2[0]) + abs(p1[1] - p2[1])

    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