LC: Campus Bikes - spiralgo/algorithms GitHub Wiki

Campus Bikes

The Essence:

Let A be the set of all possible worker-bike pairs. According to the problem statement, the priority of choosing an element from A is like this:

1. It has the shortest distance.
2. If multiple elements have same shortest distances, then it has the lowest worker-index.
3. For the 2. case, if multiple elements have the same worker-index, it has the lowest bike-index.

The algorithm needs to compare pairs according to these conditions.

There is also another intuition: So, not only that a bike needs to be the shortest bike to a worker, it also should choose this worker to be the one with the shortest distance from itself. They should thus be stable, with the bike and the worker being best matches for each other.

Details:

Implementing the basic conditions of the problem statement is quite easy using bucket sorting and priority queue. For this all pairs of workers and bikes are generated. Further information about these 2 implementations and their code can be found here: https://github.com/spiralgo/algorithms/pull/195

The intuition can be used in the following way: The bikes that a worker is closest to is found. Then the worker that the bike is closest to is found. If the first worker and the bike's worker are the same, they are matched. This generalized algorithm is called Gale–Shapley algorithm and is used in many areas of problem where matching two sets of items with minimum cost/maximum gain is needed.