-
Notifications
You must be signed in to change notification settings - Fork 0
/
406_queue_reconstruction_by_height.cpp
43 lines (39 loc) · 1.16 KB
/
406_queue_reconstruction_by_height.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
#define CATCH_CONFIG_MAIN
#include <catch.hpp>
#include <vector>
#include <random>
#include <list>
#include <map>
using namespace std;
/*
* Algorightm: Greedy
* Warning: Vector<int>, when use the first index, make sure that it will be available all the time
*/
typedef pair<int, int> PairInt;
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>> &people)
{
vector<pair<int, int>> resVec;
std::sort(people.begin(), people.end(), [&](PairInt &lhs, PairInt &rhs){
if(lhs.first > rhs.first) return true;
else if(lhs.first == rhs.first) return lhs.second < rhs.second;
else return false;
});
if(!people.empty()) resVec.push_back(people[0]);
auto it = resVec.begin();
for(int i=1; i<people.size(); ++i)
{
int index = people[i].second;
// Warning
it = resVec.begin();
resVec.insert(it+index, people[i]);
}
return resVec;
}
TEST_CASE("", "")
{
vector<PairInt> inVec1 = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
vector<PairInt> res1 = reconstructQueue(inVec1);
for(auto &p : res1) {
std::cout<<p.first<<" "<<p.second<<std::endl;
}
}