Skip to content

1066. Campus Bikes II 👍

  • Time: $O(m \cdot 2^m)$
  • Space: $O(2^m)$
 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
class Solution {
 public:
  int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
    vector<int> mem(1 << bikes.size(), INT_MAX);
    return assignBikes(workers, bikes, 0, 0, mem);
  }

 private:
  // Returns the minimum Manhattan distances to assign bikes to
  // workers[workerIndex..n), where `used` is the bitmask of the used bikes.
  int assignBikes(const vector<vector<int>>& workers,
                  const vector<vector<int>>& bikes, int workerIndex, int used,
                  vector<int>& mem) {
    if (workerIndex == workers.size())
      return 0;
    if (mem[used] != INT_MAX)
      return mem[used];

    for (int bikeIndex = 0; bikeIndex < bikes.size(); ++bikeIndex)
      if ((used >> bikeIndex & 1) == 0)
        mem[used] =
            min(mem[used], dist(workers[workerIndex], bikes[bikeIndex]) +
                               assignBikes(workers, bikes, workerIndex + 1,
                                           used | 1 << bikeIndex, mem));

    return mem[used];
  }

  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
class Solution {
  public int assignBikes(int[][] workers, int[][] bikes) {
    int[] mem = new int[1 << bikes.length];
    Arrays.fill(mem, Integer.MAX_VALUE);
    return assignBikes(workers, bikes, 0, 0, mem);
  }

  // Returns the minimum Manhattan distances to assign bikes to
  // workers[workerIndex..n), where `used` is the bitmask of the used bikes.
  private int assignBikes(int[][] workers, int[][] bikes, int workerIndex, int used, int[] mem) {
    if (workerIndex == workers.length)
      return 0;
    if (mem[used] != Integer.MAX_VALUE)
      return mem[used];

    for (int bikeIndex = 0; bikeIndex < bikes.length; bikeIndex++)
      if ((used >> bikeIndex & 1) == 0)
        mem[used] = Math.min(mem[used], dist(workers[workerIndex], bikes[bikeIndex]) +
                                            assignBikes(workers, bikes, workerIndex + 1,
                                                        used | (1 << bikeIndex), mem));

    return mem[used];
  }

  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
class Solution:
  def assignBikes(
      self,
      workers: list[list[int]],
      bikes: list[list[int]],
  ) -> int:
    def dist(p1: list[int], p2: list[int]) -> int:
      return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

    @functools.lru_cache(None)
    def dp(workerIndex: int, used: int) -> int:
      """
      Returns the minimum Manhattan distances to assign bikes to
      workers[workerIndex..n), where `used` is the bitmask of the used bikes.
      """
      if workerIndex == len(workers):
        return 0
      return min(
          (dist(workers[workerIndex],
                bike) + dp(workerIndex + 1, used | 1 << i) for i,
           bike in enumerate(bikes) if not used >> i & 1),
          default=math.inf)

    return dp(0, 0)