1057. Campus Bikes

Problem Description

The task involves assigning bikes to workers on a campus that is laid out on an X-Y coordinate plane. There are n workers and m bikes, with the condition that n <= m, meaning there are at least as many bikes as there are workers. Each worker and bike has a unique position on the plane, represented by their coordinates.

The goal is to assign each worker exactly one bike based on the shortest Manhattan distance between them. The Manhattan distance between two points p1 and p2 is defined as |p1.x - p2.x| + |p1.y - p2.y|, which essentially measures the distance between the points if you could only move along the grid horizontally or vertically.

If multiple workers could be assigned to the same bike due to equal distances, the worker with the lower index gets priority. Similarly, if one worker has the option of multiple bikes at the same distance, the bike with the lower index is assigned.

The output should be an array where each element represents the index of the bike assigned to the worker at the corresponding index.

Intuition

The solution approach requires creating a list of all possible combinations of workers and bikes along with their Manhattan distances. These combinations are then sorted primarily by the distance, then by the worker index, and finally by the bike index. This guarantees that the shortest and prioritized combinations (based on worker and bike indices) are considered first in the sorted list.

Once sorted, the algorithm iterates through the list of combinations and assigns bikes to workers one by one. During this process, both workers and bikes are marked as 'visited' to ensure that each worker gets only one bike, and each bike is assigned only once.

By sorting the combination of distances and applying the rules of priority in indexing, we ensure an efficient distribution of bikes to workers based on the proximity and predefined rules. This approach guarantees that the problem constraints will be respected and the correct assignments will be made.

Learn more about Greedy and Sorting patterns.

Solution Approach

The reference solution provided implements a straightforward but effective algorithm to solve the problem with a greedy approach. Here is a walkthrough of the solution step by step:

1. Collect Pair Information: Initially, the solution collects all possible combinations of worker and bike pairs along with their Manhattan distances. This is done using a nested loop to iterate over each worker and bike to calculate their distance: dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]).

2. Distance-Pair Array: These pairs, along with the distances, are stored in an array where each element is a tuple comprising the distance, the worker index i, and the bike index j: (dist, i, j).

3. Sorting Pair Array: Next, the tuples are sorted based on the first, second, and third elements (distance, worker index, and bike index, respectively). This orders the pairings primarily by the shortest distance, then by the smallest worker index, and lastly by the smallest bike index if there's a tie on the distance.

4. Initialize Visited Flags: Two arrays vis1 for workers and vis2 for bikes are created to keep track of whether a worker has been assigned a bike and whether a bike has been taken by a worker.

5. Assignment: The solution iterates through the sorted array and checks the visited flags for both workers and bikes. If both are unvisited, (i.e., the worker has not yet been assigned a bike and the bike has not been assigned to any worker), the bike is assigned to the worker: ans[i] = j and the visited flags are updated to True.

6. Return Assignment: Once all workers have been assigned a bike, the ans array, which holds the mapping of workers to their assigned bike indices, is returned.

It is worth noting that this approach leverages the Python's tuple sorting behavior which automatically sorts the tuples based on their first element, and in case of ties, it uses the second element, and so on. The algorithm also makes efficient use of space by using boolean arrays to keep track of the workers and bikes that have already been assigned. This algorithm achieves a balance between performance and clarity, allowing for an effective solution to the problem.

Example Walkthrough

Let's consider a small example to illustrate the solution approach with 2 workers and 3 bikes.

Initial Setup:

• Workers' coordinates: [(0, 0), (2, 1)] (Worker 0 at (0, 0) and Worker 1 at (2, 1))
• Bikes' coordinates: [(1, 0), (2, 2), (2, 3)] (Bike 0 at (1, 0), Bike 1 at (2, 2), and Bike 2 at (2, 3))

Step 1: Collect Pair Information We begin by calculating the Manhattan distance for all possible worker-bike pairs:

• Worker 0 & Bike 0: abs(0 - 1) + abs(0 - 0) = 1
• Worker 0 & Bike 1: abs(0 - 2) + abs(0 - 2) = 4
• Worker 0 & Bike 2: abs(0 - 2) + abs(0 - 3) = 5
• Worker 1 & Bike 0: abs(2 - 1) + abs(1 - 0) = 2
• Worker 1 & Bike 1: abs(2 - 2) + abs(1 - 2) = 1
• Worker 1 & Bike 2: abs(2 - 2) + abs(1 - 3) = 2

Step 2: Distance-Pair Array Construct an array with the pairs and their distances:

• [(1, 0, 0), (4, 0, 1), (5, 0, 2), (2, 1, 0), (1, 1, 1), (2, 1, 2)]

Step 3: Sorting Pair Array Sort the array of tuples by distance, then by worker index, and then by bike index:

• [(1, 0, 0), (1, 1, 1), (2, 1, 0), (2, 1, 2), (4, 0, 1), (5, 0, 2)]

Step 4: Initialize Visited Flags Create boolean arrays to track the visited workers and bikes:

• vis1 = [False, False] (for workers)
• vis2 = [False, False, False] (for bikes)

Step 5: Assignment Iterate through the sorted pairs and assign bikes to workers:

• Worker 0 is assigned Bike 0 because the pair (1, 0, 0) comes first and both Worker 0 and Bike 0 are unvisited. Mark Worker 0 and Bike 0 as visited.
• Skip to the next unvisited pair (1, 1, 1). Assign Worker 1 to Bike 1 and mark them as visited.
• Remaining pairs either contain a worker or a bike that has already been assigned, so we skip them.

Step 6: Return Assignment The ans array after the assignments is [0, 1], indicating that Worker 0 is assigned Bike 0 and Worker 1 is assigned Bike 1.

Now the assignment mapping of workers to bike indices is returned, completing the algorithm execution for the given example.

Solution Implementation

Time and Space Complexity

The time complexity and space complexity of the given code can be analyzed as follows:

Time Complexity

1. The nested loop with product(range(n), range(m)) generates all possible pairs of workers and bikes. There are n workers and m bikes, so there are n * m pairs. This operation has a time complexity of O(n * m).

2. Calculating the Manhattan distance for each worker-bike pair takes constant time, so this does not change the overall time complexity from O(n * m).

3. Appending each tuple (dist, i, j) to the arr list is done n * m times, which is also O(n * m).

4. The sort operation on arr has a time complexity of O(n * m * log(n * m)) because sorting is typically implemented with an O(n log n) complexity, and here we are sorting n * m elements.

5. The final loop goes over the sorted array, which has n * m elements, and it assigns bikes to workers. Since each worker and bike is visited at most once, the loop will run at most n + m times - because once every worker has a bike, the process stops. The time complexity for this loop is thus O(n + m).

Therefore, the overall time complexity of the code is dominated by the sorting step, which is O(n * m * log(n * m)).

Space Complexity

1. The arr list contains n * m tuples, so it has a space complexity of O(n * m).

2. The vis1 and vis2 arrays each have a space complexity of O(n) and O(m) respectively. Adding them together gives O(n + m).

3. The answer array ans has a space complexity of O(n) because it must hold an assignment for each worker.

The additional space required is for the tuples and the arrays to track the visited workers and bikes. Since these do not depend on the size of the input apart from the number of workers and bikes, we can consider them all in aggregate.

Hence, the overall space complexity is O(n * m) as it is the term that grows more significantly with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.