406. Queue Reconstruction by Height

 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

static int initialSetup = []()
{
    // toggle off cout & cin, instead, use printf & scanf
    std::ios::sync_with_stdio(false);
    // untie cin & cout
    cin.tie(NULL);
    return 0;
}
();

// observation
// we can place the people in decreasing order regarding to height,
// tie break by increasing order with regard to ppl in
// then insert (read code)
class Solution
{
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>> &people)
    {
        sort(people.begin(), people.end(),
        [](const pair<int, int> &a, const pair<int, int> &b) -> bool {
            if (a.first == b.first)
                return a.second < b.second;
            return a.first > b.first;
        });

        vector<pair<int, int>> ans;
        for (auto p : people) {
            ans.insert(ans.begin() + p.second, p);
        }

        return ans;
    }
};