Campus Bikes

medium greedy sorting manhattan distance

Problem

On a grid there are n workers and m bikes (n ≤ m), each at a point. We want to assign one unique bike to each worker. Repeatedly pick the (worker, bike) pair with the smallest Manhattan distance; ties break by smallest worker index, then smallest bike index. Once chosen, that worker and bike are removed. Return an array where answer[i] is the bike index assigned to worker i.

Inputworkers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]

Output[0, 1]

Worker 0 to bike 0 (distance 3) and worker 1 to bike 0 (distance 2) both want bike 0; the closer pair (worker 1, bike 0) is taken first, leaving worker 0 with bike 1.

workers (e.g. 0,0; 2,1)

bikes (e.g. 1,2; 3,3)

def assign_bikes(workers, bikes):
    pairs = []
    for i, (wx, wy) in enumerate(workers):
        for j, (bx, by) in enumerate(bikes):
            d = abs(wx - bx) + abs(wy - by)
            pairs.append((d, i, j))
    pairs.sort()
    ans = [-1] * len(workers)
    used_bike = [False] * len(bikes)
    for d, i, j in pairs:
        if ans[i] == -1 and not used_bike[j]:
            ans[i] = j
            used_bike[j] = True
    return ans

function assignBikes(workers, bikes) {
  const pairs = [];
  for (let i = 0; i < workers.length; i++)
    for (let j = 0; j < bikes.length; j++) {
      const d = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
      pairs.push([d, i, j]);
    }
  pairs.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
  const ans = new Array(workers.length).fill(-1);
  const usedBike = new Array(bikes.length).fill(false);
  for (const [d, i, j] of pairs)
    if (ans[i] === -1 && !usedBike[j]) { ans[i] = j; usedBike[j] = true; }
  return ans;
}

int[] assignBikes(int[][] workers, int[][] bikes) {
    List<int[]> pairs = new ArrayList<>();
    for (int i = 0; i < workers.length; i++)
        for (int j = 0; j < bikes.length; j++) {
            int d = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
            pairs.add(new int[]{ d, i, j });
        }
    pairs.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
    int[] ans = new int[workers.length];
    Arrays.fill(ans, -1);
    boolean[] usedBike = new boolean[bikes.length];
    for (int[] p : pairs)
        if (ans[p[1]] == -1 && !usedBike[p[2]]) { ans[p[1]] = p[2]; usedBike[p[2]] = true; }
    return ans;
}

vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
    vector<array<int,3>> pairs;
    for (int i = 0; i < (int)workers.size(); i++)
        for (int j = 0; j < (int)bikes.size(); j++) {
            int d = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
            pairs.push_back({ d, i, j });
        }
    sort(pairs.begin(), pairs.end());
    vector<int> ans(workers.size(), -1);
    vector<bool> usedBike(bikes.size(), false);
    for (auto& p : pairs)
        if (ans[p[1]] == -1 && !usedBike[p[2]]) { ans[p[1]] = p[2]; usedBike[p[2]] = true; }
    return ans;
}

Explanation

The rule for assigning bikes is itself greedy: repeatedly take the closest (worker, bike) pair, with ties broken by smaller worker index then smaller bike index. We can follow that rule exactly by generating all pairs, sorting them, and assigning in order.

First we build a list of every (distance, worker, bike) triple using the Manhattan distance |wx-bx| + |wy-by|. Because we store the tuple as (d, i, j) in that order, Python's normal sort gives us exactly the tie-breaking the problem wants: distance first, then worker index, then bike index.

We then walk the sorted pairs once. For each (d, i, j), if worker i is still unassigned (ans[i] == -1) and bike j is still free, we lock in that match and mark the bike used. Pairs that involve an already-taken worker or bike are simply skipped.

This works because the sort guarantees we always consider the globally best available pair before any worse one, which is precisely the stated process.

Example: workers=[[0,0],[2,1]], bikes=[[1,2],[3,3]]. Worker 0 to bike 0 has distance 3, the smallest, so it is matched first; worker 1 then takes bike 1, giving [0, 1].

Time: O(nm log(nm)) Space: O(nm)