31. Leetcode 406. Queue Reconstruction by Height.md

406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

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]]

---

Solutions

Method1: Naive Approach

/*
/*
Method1: Naive Approach + Gready

each person has value and number, where number is # of people in front that are equal or greater in height

step1: sorting people by the # of people in front with heights equal or greater, this is to make sure 
        there are enough people in front when considering individual person.
step2: insert each person p1 to a list:
       1. insert directly if list is empty
       2. insert before a person p2 in list that has equal or greater height compared to p1 and # of people with equal or greater
          height before p2 equals p1.number
       3. insert at last if neither 1 nor 2 is met
       
T(n) = O(nlgn) + O(n^2), where nlgn is for sorting
S(n) = O(n)
*/

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //sort by the # of person in front
        sort(people.begin(), people.end(),[](const vector<int>& a, const vector<int>& b)->bool{
                return a[1] < b[1];            
        });

        //insert each person into appropriate position in the queue
        list<vector<int>> myList;
        for(auto& p : people){
            if(myList.empty()){
                myList.insert(myList.begin(),p);
            }
            else{
                int count = 0;
                auto it = myList.begin();
                for(; it != myList.end(); it++){
                    if(count == p[1] && (*it)[0] >= p[0]){
                        break;
                    }
                    if((*it)[0] >= p[0]){
                        count++;
                    }
                }
                myList.insert(it,p);
            }
        }
        vector<vector<int>> res;
        for(auto it = myList.begin(); it != myList.end(); it++){
            res.push_back(*it);
        }
        return res;
    }
};