Campus Bikes - Leetcode Solution

Campus Bikes is a problem on LeetCode that can be solved using a straightforward approach. It involves finding the shortest distance between all pairs of workers and bikes in a campus with multiple workers and bikes. Here are the steps to solve the problem:

1. Iterate over all possible combinations of workers and bikes and calculate the Manhattan distance between them. Manhattan distance is simply the sum of absolute differences between x and y coordinates of two points. Store the distances in a priority queue sorted by the distance.

2. Iterate over the priority queue and pop out the closest pair. Add the worker-bike pair to the result only if neither of them has been assigned to a pair before. Mark the worker and bike as "assigned" to prevent them from being assigned to multiple pairs.

3. Continue step 2 until all pairs have been assigned.

Here is the code to solve the problem:

def assignBikes(workers, bikes):
    distances = []
    for i, worker in enumerate(workers):
        for j, bike in enumerate(bikes):
            distance = abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
            distances.append((distance, i, j))

    distances.sort()    # sort the distances in ascending order

    result = [-1] * len(workers)    # initialize the result with -1


    assigned_workers = set()
    assigned_bikes = set()


    for distance, i, j in distances:
        if i not in assigned_workers and j not in assigned_bikes:
            result[i] = j    # assign the bike to worker i
            assigned_workers.add(i)
            assigned_bikes.add(j)

    return result

The time complexity of the algorithm is O(N^2 log N), where N is the maximum of the number of workers and bikes. This is because we are iterating over all possible combinations of workers and bikes and sorting the distances using a priority queue.

1