We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Campus Bikes II

Number: 1067

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a list of n workers and m bikes, each represented as 2D coordinates on a grid (with n ≤ m), assign each worker exactly one unique bike such that the sum of the Manhattan distances between assigned workers and bikes is minimized. The Manhattan distance between two points (x1, y1) and (x2, y2) is given by |x1 - x2| + |y1 - y2|.

Key Insights

  • The problem is a variant of the assignment problem which can be solved using Dynamic Programming (DP) with bitmasking due to the small constraints (n, m ≤ 10).
  • A bitmask can represent which bikes have already been assigned. For example, if m = 3, then mask = 101 means bikes 0 and 2 have been taken.
  • The state of the DP can be represented using two parameters: the current worker index and the bitmask representing the used bikes.
  • Recursively assign bikes to workers by iterating over available bikes and take the minimum cumulative Manhattan distance.
  • Memoization is key to avoid duplicate computations in overlapping subproblems.

Space and Time Complexity

Time Complexity: O(m * 2^m) in the worst case, since for each of the 2^m states, we try assigning up to m bikes. Space Complexity: O(2^m), for storing the DP results (memoization cache).

Solution

The solution uses recursion with memoization (DP with bitmasking). We define a helper function dp(worker, mask) where worker is the index of the current worker to assign a bike and mask is an integer representing the set of bikes already taken. For each worker, we iterate through all bikes and if a bike is not already assigned (checked using the bitmask), we calculate the Manhattan distance from the current worker to this bike and recursively assign the remaining workers. The result for each state is memoized to avoid recomputation. The base case occurs when all workers have been assigned bikes.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java.

from functools import lru_cache

def assignBikes(workers, bikes):
    # Helper function to compute Manhattan distance between two points
    def manhattan(p1, p2):
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    
    n = len(workers)
    m = len(bikes)
    
    # dp(worker, mask): minimum total Manhattan distance starting from worker index 'worker'
    # with bikes represented by 'mask' (1 bit per bike, 1 means assigned)
    @lru_cache(maxsize=None)
    def dp(worker, mask):
        # Base case: if all workers are assigned, return 0
        if worker == n:
            return 0
        
        res = float('inf')
        # Iterate over all bikes
        for j in range(m):
            # Check if bike j is free
            if not (mask & (1 << j)):
                # Calculate new mask with bike j assigned and compute total cost
                new_mask = mask | (1 << j)
                cost = manhattan(workers[worker], bikes[j]) + dp(worker + 1, new_mask)
                res = min(res, cost)
        return res
    
    # Start with the first worker and no bikes assigned (mask = 0)
    return dp(0, 0)

# Example usage:
# workers = [[0,0], [2,1]]
# bikes = [[1,2], [3,3]]
# print(assignBikes(workers, bikes))
← Back to All Questions