Skip to content

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<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]);
  }
};

 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<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]);
  }
}

 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
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