-
Notifications
You must be signed in to change notification settings - Fork 0
/
CampusBikes.cpp
78 lines (74 loc) · 2.16 KB
/
CampusBikes.cpp
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
75
76
77
78
//Approach 1
//using priority queue
class Solution {
public:
struct Dis{
int d;
int worker;
int bike;
bool operator<(const Dis& x) const {
if(x.d != d){
return d > x.d;
}
if(worker != x.worker){
return worker > x.worker;
}
return bike > x.bike;
}
};
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
vector<int> res(workers.size(), -1);
priority_queue<Dis> q;
for(int i= 0; i<workers.size(); i++){
for(int j = 0; j<bikes.size(); j++){
int d = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
q.push({d, i, j});
}
}
vector<bool> visitedBike(bikes.size(), false);
while(!q.empty()){
auto [d, i, j] = q.top();
q.pop();
if(res[i] == -1 && visitedBike[j] == false){
visitedBike[j] = true;
res[i] = j;
}
}
return res;
}
};
//Approach 2
//Using bucket sort
class Solution {
public:
vector<int> assignBikes(vector<vector<int>>& W, vector<vector<int>>& B) {
//using bucket sort
int workers = W.size();
int bikes = B.size();
vector<int> res(workers, -1);
vector<bool> occ(1000, false);
array<vector<unsigned int>, 2000 > m;
for(int i= 0; i< workers ; i++){
for(int j = 0; j< bikes; j++){
int d = abs(W[i][0] - B[j][0]) + abs(W[i][1] - B[j][1]);
m[d].push_back(i<<16 | j);
}
}
int c = 0;
for(int dist = 0; dist < 2000; dist++){
for(auto x : m[dist]){
int bike = x & 0xFFFF;
int worker = x>>16;
if(occ[bike] == false && res[worker] ==-1){
res[worker] = bike;
occ[bike] = true;
c++;
}
if(c == workers){
return res;
}
}
}
return res;
}
};