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

Number: 1052

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given positions of workers and bikes on a 2D plane, assign each worker a bike. Choose the (worker, bike) pair with the smallest Manhattan distance. When distances are tied, assign the pair with the smallest worker index first, and if still tied, assign the one with the smallest bike index. Continue this process until every worker has a bike, and return the bike index assigned to each worker.

Key Insights

  • Compute the Manhattan distance between every worker and bike pair.
  • To achieve the tie-breaking rules, sort all pairs by distance, then by worker index and bike index.
  • Once a worker is assigned a bike, skip any other pairs involving that worker or the already assigned bike.
  • The problem can also be approached using bucket sort because the Manhattan distance range is limited, but sorting is intuitive given the constraints.

Space and Time Complexity

Time Complexity: O(n * m * log(n * m)) where n is the number of workers and m is the number of bikes. Space Complexity: O(n * m) for storing all worker-bike pairs.

Solution

Create all possible (worker, bike) pairs along with their Manhattan distances. Sort this list of pairs by:

  1. Manhattan distance,
  2. Worker index (if distances are equal),
  3. Bike index (if both distance and worker index are equal).

Then, iterate over the sorted list and assign bikes to workers if neither the worker nor the bike has already been assigned. This guarantees that at each step, the optimal available pairing (according to the problem’s requirements) is made. This method naturally enforces the tie-breaking rules specified in the problem.

Code Solutions

# Python solution

def assign_bikes(workers, bikes):
    # List to hold all possible (distance, worker, bike) tuples
    pairs = []
    for worker_index, (wx, wy) in enumerate(workers):
        for bike_index, (bx, by) in enumerate(bikes):
            # Calculate Manhattan distance between worker and bike
            distance = abs(wx - bx) + abs(wy - by)
            pairs.append((distance, worker_index, bike_index))
    
    # Sort pairs based on distance, then worker index, then bike index
    pairs.sort()
    
    n = len(workers)               # Number of workers
    assigned_workers = [False] * n  # Track if worker is already assigned
    assigned_bikes = [False] * len(bikes)  # Track if bike is already assigned
    result = [-1] * n              # Result list to store bike assignment for each worker
    
    # Iterate over the sorted pairs and assign bikes
    for distance, worker_index, bike_index in pairs:
        if not assigned_workers[worker_index] and not assigned_bikes[bike_index]:
            result[worker_index] = bike_index  # Assign bike to worker
            assigned_workers[worker_index] = True  # Mark worker as assigned
            assigned_bikes[bike_index] = True      # Mark bike as assigned
    return result

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