Problem Description

The "Campus Bikes" problem asks you to assign bikes to workers on a campus grid. Each worker and bike has a location represented by a pair of coordinates. The goal is to assign each worker exactly one bike, such that:

• Each worker is assigned one unique bike (no two workers share a bike).
• Bikes cannot be reused.
• Each worker must get the bike that is closest to them (using Manhattan distance), and if there are ties, you must break them first by worker index, then by bike index.

The function receives two lists: workers and bikes, both containing coordinate pairs. The output should be a list result where result[i] is the index of the bike assigned to the ith worker.

Thought Process

At first glance, the problem resembles an assignment or matching problem. The most straightforward approach is to compute the distance from each worker to every bike and, for each worker, always pick the nearest available bike. However, since bike assignments are exclusive, we need to ensure that no two workers are assigned the same bike.

A brute-force solution would try every possible assignment, but this quickly becomes infeasible as the number of workers and bikes grows. Therefore, we need a more efficient way to ensure that workers are assigned their closest available bikes, while handling tie-breakers as specified.

The key insight is to process all possible worker-bike pairs, sorted by distance (and then by worker and bike index), and for each pair, assign the bike to the worker if both are still unassigned. This greedy approach ensures that assignments are made in the required priority order.

Solution Approach

The optimized solution leverages sorting and greedy assignment. Here’s a step-by-step breakdown:

1. Compute all distances: For every worker and every bike, calculate the Manhattan distance between them. Store each as a tuple: (distance, worker_index, bike_index).
2. Sort all pairs: Sort the list of tuples first by distance, then by worker index, then by bike index. This ensures that the closest pairs are considered first, and ties are broken as specified.
3. Assign bikes greedily: Initialize arrays to track whether a worker or bike has been assigned. Iterate through the sorted list, and for each pair, assign the bike to the worker if both are still unassigned.
4. Output the assignments: Once all workers have bikes, return the assignments as a list where the i-th element is the index of the bike assigned to the i-th worker.

This approach is efficient because sorting all pairs is manageable for the given constraints, and assignment is done in a single pass.

Example Walkthrough

Suppose we have the following input:

• workers = [[0,0],[2,1]]
• bikes = [[1,2],[3,3]]

Step 1: Compute all distances

• Worker 0 to Bike 0: |0-1| + |0-2| = 3
• Worker 0 to Bike 1: |0-3| + |0-3| = 6
• Worker 1 to Bike 0: |2-1| + |1-2| = 2
• Worker 1 to Bike 1: |2-3| + |1-3| = 3

Step 2: Sort pairs
Sorted list: [(2,1,0), (3,0,0), (3,1,1), (6,0,1)]

Step 3: Assign bikes

• (2,1,0): Worker 1 and Bike 0 are unassigned. Assign Bike 0 to Worker 1.
• (3,0,0): Bike 0 already assigned, skip.
• (3,1,1): Worker 1 already assigned, skip.
• (6,0,1): Worker 0 and Bike 1 are unassigned. Assign Bike 1 to Worker 0.

Result: Worker 0 gets Bike 1, Worker 1 gets Bike 0. Output: [1, 0]

Time and Space Complexity

Brute-force approach:
Trying all possible assignments is O((N!) * N), where N is the number of workers/bikes. This is not feasible for large N.

Optimized approach:

• Computing all distances: O(N*M), where N is number of workers and M is number of bikes.
• Sorting all pairs: O(N*M*log(N*M))
• Greedy assignment: O(N*M)

Overall, the time complexity is O(N*M*log(N*M)), and space complexity is O(N*M) for storing all pairs.

Summary

The "Campus Bikes" problem is elegantly solved by precomputing all possible worker-bike distances and sorting them according to the rules. By greedily assigning the closest available bikes, we ensure correctness and efficiency. The use of sorting and simple assignment tracking makes the solution both intuitive and powerful, avoiding the pitfalls of brute-force approaches.

Code Implementation

class Solution:
    def assignBikes(self, workers, bikes):
        pairs = []
        for i, (wx, wy) in enumerate(workers):
            for j, (bx, by) in enumerate(bikes):
                dist = abs(wx - bx) + abs(wy - by)
                pairs.append((dist, i, j))
        pairs.sort()
        res = [-1] * len(workers)
        assigned_bikes = set()
        assigned_workers = set()
        count = 0
        for dist, i, j in pairs:
            if i not in assigned_workers and j not in assigned_bikes:
                res[i] = j
                assigned_workers.add(i)
                assigned_bikes.add(j)
                count += 1
                if count == len(workers):
                    break
        return res
      

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        vector<tuple<int, int, int>> pairs;
        int n = workers.size(), m = bikes.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                pairs.push_back({dist, i, j});
            }
        }
        sort(pairs.begin(), pairs.end());
        vector<int> res(n, -1);
        vector<bool> worker_assigned(n, false), bike_assigned(m, false);
        int count = 0;
        for (auto& p : pairs) {
            int dist, i, j;
            tie(dist, i, j) = p;
            if (!worker_assigned[i] && !bike_assigned[j]) {
                res[i] = j;
                worker_assigned[i] = true;
                bike_assigned[j] = true;
                count++;
                if (count == n) break;
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
        List<int[]> pairs = new ArrayList<>();
        int n = workers.length, m = bikes.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int dist = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                pairs.add(new int[]{dist, i, j});
            }
        }
        pairs.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int[] res = new int[n];
        Arrays.fill(res, -1);
        boolean[] workerAssigned = new boolean[n];
        boolean[] bikeAssigned = new boolean[m];
        int count = 0;
        for (int[] p : pairs) {
            int dist = p[0], i = p[1], j = p[2];
            if (!workerAssigned[i] && !bikeAssigned[j]) {
                res[i] = j;
                workerAssigned[i] = true;
                bikeAssigned[j] = true;
                count++;
                if (count == n) break;
            }
        }
        return res;
    }
}
      

var assignBikes = function(workers, bikes) {
    let pairs = [];
    for (let i = 0; i < workers.length; i++) {
        for (let j = 0; j < bikes.length; j++) {
            let dist = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
            pairs.push([dist, i, j]);
        }
    }
    pairs.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    let res = new Array(workers.length).fill(-1);
    let assignedBikes = new Set();
    let assignedWorkers = new Set();
    let count = 0;
    for (let [dist, i, j] of pairs) {
        if (!assignedWorkers.has(i) && !assignedBikes.has(j)) {
            res[i] = j;
            assignedWorkers.add(i);
            assignedBikes.add(j);
            count++;
            if (count === workers.length) break;
        }
    }
    return res;
};