On a campus represented on the X-Y, there are n workers and m bikes (n <= m). You are given:

• workers: an array of length n, where workers[i] = [xi, yi] is the position of the ith worker
• bikes: an array of length m, where bikes[j] = [xj, yj] is the position of the jth bike

Assign a bike to each worker by pairing the worker and bike with the shortest Manhattan distance between them. If there are multiple pairs with the same distance, choose the pair with the smallest worker index, and if still tied, choose the pair with the smallest bike index. Return an array answer of length n, where answer[i] is the 0-indexed index of the bike assigned to the ith worker.

Note: The Manhattan distance between two points p1 and p2 is |p1.x – p2.x| + |p1.y – p2.y|.

Example:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
Explanation: Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: [0,2,1]
Explanation: Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

Approach:

We want to organize the (worker, bike) pairs in ascending order, prioritizing their Manhattan distance, then worker index, and then bike index. Therefore, we will generate all possible (worker, bike) pairs and sort them according to the previously listed priorities. We will then iterate over the pairs, if both the worker and bike are available, assign the bike to the worker, and mark them both as unavailable. We will repeat this process until all workers have been assigned a bike.

Steps-by-step approach:

• Initialize Data Structures:
  • Create an array allTriplets to store tuples of (distance, worker, bike).
  • Create an arrayr bikeStatus to keep track of which bikes are taken.
  • Create an array workerStatus to keep track of which bike is assigned to each worker.
• Generate All Possible Pairs:
  • Iterate through all the workers and all the bikes.
  • For each worker-bike pair, calculate the Manhattan distance using the findDistance() function.
  • Add a tuple (distance, worker, bike) to the allTriplets array.
• Sort the Triplets:
  • Sort the allTriplets array based on the distance in ascending order.
• Assign Bikes to Workers:
  • Iterate through the sorted allTriplets.
  • For each tuple, check if the worker and the bike are both free.
  • If they are, assign the bike to the worker by updating the bikeStatus and workerStatus vectors.
  • Increment the pairCount variable.
  • If all workers have been assigned a bike, return the workerStatus vector.
• Return the Final Assignments:
  • After the loop, return the workerStatus vector, which contains the index of the bike assigned to each worker.

Below is the implementation of the above approach:

#include <bits/stdc++.h> // for sort
using namespace std;

// Function to return the Manhattan distance
int findDistance(vector<int>& worker, vector<int>& bike)
{
    return abs(worker[0] - bike[0])
           + abs(worker[1] - bike[1]);
}

vector<int> assignBikes(vector<vector<int> >& workers,
                        vector<vector<int> >& bikes)
{
    // List of WorkerBikeTuples's to store all the possible
    // triplets (distance, worker, bike)
    vector<vector<int> > allTriplets;

    // Generate all the possible pairs
    for (int worker = 0; worker < workers.size();
         worker++) {
        for (int bike = 0; bike < bikes.size(); bike++) {
            int distance = findDistance(workers[worker],
                                        bikes[bike]);
            allTriplets.push_back(
                { distance, worker, bike });
        }
    }

    // Sort the triplets based on distance (ascending order)
    sort(allTriplets.begin(), allTriplets.end());

    // Initialize all values to false, to signify no bikes
    // have been taken
    vector<int> bikeStatus(bikes.size(), false);
    // Initialize all indices to -1, to signify no worker
    // has a bike
    vector<int> workerStatus(workers.size(), -1);
    // Keep track of how many worker-bike pairs have been
    // made
    int pairCount = 0;

    for (auto t : allTriplets) {
        int dist = t[0];
      int worker = t[1];
      int bike = t[2];
        // If both worker and bike are free, assign them to
        // each other
        if (workerStatus[worker] == -1
            && !bikeStatus[bike]) {
            bikeStatus[bike] = true;
            workerStatus[worker] = bike;
            pairCount++;

            // If all the workers have a bike assigned, we
            // can stop
            if (pairCount == workers.size()) {
                return workerStatus;
            }
        }
    }

    return workerStatus;
}

int main()
{
    // Driver code to test the function
    vector<vector<int> > workers = { { 0, 0 }, { 2, 1 } };
    vector<vector<int> > bikes = { { 1, 2 }, { 3, 3 } };

    vector<int> assignments = assignBikes(workers, bikes);

    cout << "Worker assignments (bike index for each "
                 "worker): ";
    for (int assignment : assignments) {
        cout << assignment << " ";
    }
    cout << endl;

    return 0;
}

import java.util.*;

public class BikeAssignment {

    // Function to return the Manhattan distance
    public static int findDistance(int[] worker, int[] bike) {
        return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
    }

    public static int[] assignBikes(int[][] workers, int[][] bikes) {
        // List of all possible triplets (distance, worker, bike)
        List<int[]> allTriplets = new ArrayList<>();

        // Generate all the possible pairs
        for (int worker = 0; worker < workers.length; worker++) {
            for (int bike = 0; bike < bikes.length; bike++) {
                int distance = findDistance(workers[worker], bikes[bike]);
                allTriplets.add(new int[]{distance, worker, bike});
            }
        }

        // Sort the triplets based on distance (ascending order)
        allTriplets.sort(Comparator.comparingInt(a -> a[0]));

        // Initialize all values to false, to signify no bikes have been taken
        boolean[] bikeStatus = new boolean[bikes.length];
        // Initialize all indices to -1, to signify no worker has a bike
        int[] workerStatus = new int[workers.length];
        Arrays.fill(workerStatus, -1);

        // Keep track of how many worker-bike pairs have been made
        int pairCount = 0;

        for (int[] t : allTriplets) {
            int dist = t[0];
            int worker = t[1];
            int bike = t[2];
            // If both worker and bike are free, assign them to each other
            if (workerStatus[worker] == -1 && !bikeStatus[bike]) {
                bikeStatus[bike] = true;
                workerStatus[worker] = bike;
                pairCount++;

                // If all the workers have a bike assigned, we can stop
                if (pairCount == workers.length) {
                    return workerStatus;
                }
            }
        }

        return workerStatus;
    }

    public static void main(String[] args) {
        // Driver code to test the function
        int[][] workers = { { 0, 0 }, { 2, 1 } };
        int[][] bikes = { { 1, 2 }, { 3, 3 } };

        int[] assignments = assignBikes(workers, bikes);

        System.out.print("Worker assignments (bike index for each worker): ");
        for (int assignment : assignments) {
            System.out.print(assignment + " ");
        }
        System.out.println();
    }
}
// This code is contributed by Ayush Mishra

def find_distance(worker, bike):
    """Calculate the Manhattan distance between a worker and a bike."""
    return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])

def assign_bikes(workers, bikes):
    """Assign bikes to workers based on the minimum Manhattan distance."""
    # List of tuples to store all the possible triplets (distance, worker, bike)
    all_triplets = []

    # Generate all the possible pairs
    for worker_index, worker in enumerate(workers):
        for bike_index, bike in enumerate(bikes):
            distance = find_distance(worker, bike)
            triplet = (distance, worker_index, bike_index)
            all_triplets.append(triplet)

    # Sort the triplets based on distance (ascending order)
    all_triplets.sort()

    # Initialize the assignment arrays
    worker_assigned = [-1] * len(workers)
    bike_taken = [False] * len(bikes)
    
    # Assign bikes to workers
    for distance, worker, bike in all_triplets:
        if worker_assigned[worker] == -1 and not bike_taken[bike]:
            worker_assigned[worker] = bike
            bike_taken[bike] = True
            
            # If all the workers have a bike assigned, we can stop
            if all(assignment != -1 for assignment in worker_assigned):
                break

    return worker_assigned

def main():
    """Driver code to test the function."""
    workers = [[0, 0], [2, 1]]
    bikes = [[1, 2], [3, 3]]

    assignments = assign_bikes(workers, bikes)

    print("Worker assignments (bike index for each worker):", assignments)

if __name__ == "__main__":
    main()
    
# This code is contributed by Shivam Gupta

// JavaScript program for the above approach

// Function to return the Manhattan distance
function findDistance(worker, bike) {
    return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
}

function assignBikes(workers, bikes) {
    // List of all triplets (distance, worker, bike)
    let allTriplets = [];

    // Generate all possible pairs
    for (let worker = 0; worker < workers.length; worker++) {
        for (let bike = 0; bike < bikes.length; bike++) {
            let distance = findDistance(workers[worker], bikes[bike]);
            allTriplets.push([distance, worker, bike]);
        }
    }

    // Sort the triplets based on distance (ascending order)
    allTriplets.sort((a, b) => a[0] - b[0]);

    // Initialize bikeStatus and workerStatus arrays
    let bikeStatus = new Array(bikes.length).fill(false);
    let workerStatus = new Array(workers.length).fill(-1);

    // Keep track of how many worker-bike pairs have been made
    let pairCount = 0;

    for (let t of allTriplets) {
        let dist = t[0];
        let worker = t[1];
        let bike = t[2];

        // If both worker and bike are free, assign them to each other
        if (workerStatus[worker] === -1 && !bikeStatus[bike]) {
            bikeStatus[bike] = true;
            workerStatus[worker] = bike;
            pairCount++;

            // If all the workers have a bike assigned, we can stop
            if (pairCount === workers.length) {
                return workerStatus;
            }
        }
    }

    return workerStatus;
}

// Driver code to test the function
let workers = [[0, 0], [2, 1]];
let bikes = [[1, 2], [3, 3]];

let assignments = assignBikes(workers, bikes);

console.log("Worker assignments (bike index for each worker):", assignments);

// This code is contributed by Susobhan Akhuli

Worker assignments (bike index for each worker): 1 0 

Time complexity: O(NMlog⁡(NM)), Here, N is the number of workers, and M is the number of bikes.
Auxiliary Space: O(NM)