Problem description:

In 2D space, m people, n bikes, with the following conditions

  1. m< n
  2. does not exist two people that have same distance, abs(x1-x2)+abs(y1-y2), between a bike.
  3. everyone would find the bike that is the most closest to himself. If a bike is occupied, others can not use it.
    1
    2
    3
    4
    5
    OPOBOOP
    OOOOOOO
    OOOOOOO
    OOOOOOO
    BOOBOOB

Solution guidline:

  1. 需要跟面试官讨论清楚他需要的最佳匹配是什么

  2. 如果是要求全局人车距离最短

    1. 二分图的最佳匹配问题，使用匈牙利算法，参考题目https://blog.csdn.net/u011721440/article/details/38169201
    2. 发现这里不能使用max flow， 因为这个bipartite is a weighted graph. 参考 https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/

  3. 如果是要求最佳匹配只是给每个人匹配到车，可以用PQ+Map

PQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#include <unordered_map>
#include <vector>
#include <list>
#include <queue>
#include <unordered_set>

using namespace std;

class BikeMatching{
public:
    BikeMatching(vector<vector<char>>& graph);
    //void init();
    void matching();

    vector<vector<int>> people;
    vector<vector<int>> bikes;
    vector<pair<int, int>> res;
    priority_queue<pair<int, pair<int, int>>> pq;
    unordered_set<int> visited_man, visited_bike;
};

BikeMatching::BikeMatching(vector<vector<char>>& graph){
    if(graph.empty())
        return;

    for (int i = 0; i < graph.size(); i++){
        for (int j = 0; j < graph[0].size(); j++){
            if(graph[i][j] == 'O') continue;
            else if(graph[i][j] == 'P')
                people.push_back(vector<int>{i, j});
            else if(graph[i][j] == 'B')
                bikes.push_back(vector<int>{i, j});
            else
                printf("incorrect input\n");
        }
    }

    for (int i = 0; i < people.size(); i++){
        for (int j = 0; j < bikes.size(); j++){
            int dis = abs(people[i][0]- bikes[j][0]) + abs(people[i][1] - bikes[j][1]);
            pq.push(make_pair(-dis, make_pair(i, j)));
        }
    }
}

void BikeMatching::matching()
{
    while(visited_man.size() != people.size()){
        auto tmp = pq.top(); pq.pop();
        if(visited_man.count(tmp.second.first) || visited_bike.count(tmp.second.second))
            continue;

        visited_man.insert(tmp.second.first);
        visited_bike.insert(tmp.second.second);
        res.push_back(tmp.second);
    }

    for(auto r: res){
        printf("people at (%d, %d), pairs with (%d, %d)\n", people[r.first][0], people[r.first][1], bikes[r.second][0], bikes[r.second][1]);
    }
}

int main()
{
    vector<vector<char>> graph{
        {'O', 'P', 'O', 'B', 'P', 'O', 'P'},
        {'O', 'O', 'O', 'O', 'O', 'O', 'O'},
        {'B', 'O', 'O', 'B', 'O', 'O', 'B'}};

    BikeMatching ins(graph);
    ins.matching();
    return 0;
}

time complexity: $O()$
space complexity: $O()$
reference:
http://www.cnblogs.com/jackge/archive/2013/05/03/3057028.html
https://www.careercup.com/question?id=5687196447670272