Solution to Leetcode 406. Queue Reconstruction by Height

Problem statement could be found @https://leetcode.com/problems/queue-reconstruction-by-height/


Input -
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Approach -


Arrange the inputs first in decreasing order of height, so it would start looking like
[7,0],,[7,1]
[6,1],
[5,0],[5,2]
[4,4]

Now pick one element at a time and put it at index  k

First we pick [7,0] since this is the only element O/P vector is [7,0]
Next we pick [7,1] since its index is 1 we will put it at index 1 in O/P vector [7,0],[7,1]
Next we pick  [6,1] and place it index 1 so O/P vector is [7,0],[6,1],[7,1]
Next we pick  [5,0] and place it index 0 so O/P vector is [5,0],[7,0],[6,1],[7,1]
Next we pick  [5,2] and place it index 2 so O/P vector is [5,0],[7,0],[5,2],[6,1],[7,1]
Next we pick  [4,4] and place it index 4 so O/P vector is [5,0],[7,0],[5,2],[6,1],[4,4],[7,1]

Following is the code for above logic in C++

class Solution {
    private:
    struct compare
    {
        bool operator()(const pair<int, int> &p1,const pair<int, int> &p2) const{
          // ensures greater height comes first
            if (p1.first > p2.first)
                return true;
           // if there is tiebreak in height, then put smaller k index first
            if ( (p1.first == p2.first ) && (p1.second < p2.second))  
                return true;
            return false;  
           
        }
    };
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
       
        vector<pair<int, int>> retVal;
        if (people.size() == 0)
            return retVal;
        std::sort(people.begin(), people.end(), compare());
     
     
        retVal.push_back(people[0]);
     
        for(int i=1;i<people.size();i++){
            pair<int, int> px = people[i];
            retVal.insert(retVal.begin() + px.second, px);
         
        }
        return retVal;
    }
};