Formatted question description: https://leetcode.ca/all/1066.html

1066. Campus Bikes II

Level

Medium

Description

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Image text

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]

Output: 6

Explanation:

We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Image text

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]

Output: 4

Explanation:

We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

  1. 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
  2. All worker and bike locations are distinct.
  3. 1 <= workers.length <= bikes.length <= 10

Solution

Since the number of workers and the number of bikes are limited, this problem can be solved using dynamic programming with compressed states. For each (worker, bike) pair, calculate the Manhattan distance between the worker and the bike. Create a 2D array dp with 1 << N rows and 1 << M columns, and initialize all elements to Integer.MAX_VALUE. Then for 0 <= i < N and 0 <= j < M, set dp[1 << i][1 << j] to the distance between workers[i] and bikes[j]. Here dp[i][j] means the minimum possible sum of Manhattan distances between workers and bikes where workers in bits of i are selected and workers in bits of j are selected.

For each element dp[i][j], obtain its value using each possible worker and each possible bike, and the value is obtained from the previous state. Maintain the minimum value.

Finally, return the minimum value in the last row of dp.

class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
        int workersLength = workers.length, bikesLength = bikes.length;
        int[][] distances = new int[workersLength][bikesLength];
        for (int i = 0; i < workersLength; i++) {
            int[] worker = workers[i];
            for (int j = 0; j < bikesLength; j++) {
                int[] bike = bikes[j];
                distances[i][j] = manhattanDistance(worker, bike);
            }
        }
        int[] ret = new int[workersLength];
        boolean[] workersAssigned = new boolean[workersLength];
        boolean[] bikesAssigned = new boolean[bikesLength];
        for (int i = 0; i < workersLength; i++) {
            int minDistance = Integer.MAX_VALUE;
            int minWorkerIndex = -1, minBikeIndex = -1;
            for (int j = 0; j < workersLength; j++) {
                if (workersAssigned[j])
                    continue;
                for (int k = 0; k < bikesLength; k++) {
                    if (bikesAssigned[k])
                        continue;
                    int distance = distances[j][k];
                    if (distance < minDistance) {
                        minDistance = distance;
                        minWorkerIndex = j;
                        minBikeIndex = k;
                    }
                }
            }
            ret[minWorkerIndex] = minBikeIndex;
            workersAssigned[minWorkerIndex] = true;
            bikesAssigned[minBikeIndex] = true;
        }
        return ret;
    }

    public int manhattanDistance(int[] point1, int[] point2) {
        return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
    }
}

All Problems

All Solutions