MediumArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Campus Bikes II

1 approach, code in every language

On a campus grid you are given the positions of n workers and m bikes, each as [x, y] coordinates, with n <= m. You must assign each worker exactly one distinct bike.

The cost of an assignment is the sum over all workers of the Manhattan distance between a worker and the bike given to that worker. Return the minimum possible total Manhattan distance across all valid assignments.

Example 1

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

Output: 6

Worker 0 takes bike 0 (distance 3) and worker 1 takes bike 1 (distance 3), giving a total of 6, which beats the alternative assignment.

Example 2

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

Output: 4

Assigning bike 0 to worker 0, bike 2 to worker 1, and bike 1 to worker 2 yields the minimum total distance of 4.

Constraints

n == workers.length
m == bikes.length
1 <= n <= m <= 10
workers[i].length == bikes[j].length == 2
0 <= xi, yi < 1000
All worker and bike locations are unique.

Bitmask Dynamic Programming

Track which bikes are used with a bitmask; dp[mask] is the best cost to assign the first popcount(mask) workers using exactly the bikes in mask.

Loading animation…

Intuition

Because there are at most 10 bikes, the set of used bikes fits in a small bitmask. We assign workers in a fixed order: the number of set bits in a mask tells us how many workers have already been placed, so the next worker to serve is worker index popcount(mask). We define dp[mask] as the minimum total distance to assign that many workers using precisely the bikes selected in mask. To extend a state we hand the next worker any bike that is still free, forming a new mask with one more bit set. Reading off the minimum over all masks that use exactly n bikes gives the optimal assignment cost.

Algorithm walkthrough

1Let m be the number of bikes and allocate dp over all 2^m masks, filled with infinity except dp[0] = 0.
2Process masks in increasing order; for each reachable mask compute worker = popcount(mask).
3If worker equals n, all workers are assigned, so update the answer with dp[mask] and skip expansion.
4Otherwise, for every bike b not present in mask, form nxt = mask | (1 << b).
5Relax dp[nxt] with dp[mask] plus the Manhattan distance between worker and bike b.
6After scanning all masks, return the minimum dp value over masks containing exactly n bikes.

Implementation

class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        n, m = len(workers), len(bikes)
        INF = float('inf')
        dp = [INF] * (1 << m)
        dp[0] = 0

        def dist(w: List[int], b: List[int]) -> int:
            return abs(w[0] - b[0]) + abs(w[1] - b[1])

        ans = INF
        for mask in range(1 << m):
            worker = bin(mask).count('1')
            if dp[mask] == INF:
                continue
            if worker == n:
                ans = min(ans, dp[mask])
                continue
            for b in range(m):
                if not (mask & (1 << b)):
                    nxt = mask | (1 << b)
                    cost = dp[mask] + dist(workers[worker], bikes[b])
                    if cost < dp[nxt]:
                        dp[nxt] = cost
        return ans

Time

O(2^m * m)

Space

O(2^m)

There are 2^m masks and each expands to at most m bikes; m <= 10 keeps this tractable.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free