Easy Solution


  • 0
    H

    My Solution :

    1. First sort the people based on height.
    2. Get the First Person .i.e. The shortest guy in the sorted people with 0 No. of persons in front of him.
    3. Now iterate through remaining people in the sorted people. And check if the respective person is a perfect match at that point if yes add him to result and remove from sorted people. Or else proceed with next.
    4. Repeat the process till there are none remaining in sorted people.
    class Solution {
    public:
        bool IsSameAsPresent(vector<pair<int, int>>& Q,pair<int, int> item){
            //Checks if the present count of people in Q is equal to the item's k
            int count=0;
            for(int i=0;i<Q.size();i++)
            {
                if (Q[i].first >= item.first)
                    ++count;
            }
            return (count == item.second);
        }
        
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            
            vector<pair<int, int>> Q;
            //Arrange the People based on height
                sort(people.begin(), people.end());
                     
            //Lets get the 1st shortest person 
                for(int i=0;i<people.size();i++)
                {
                    if(people[i].second ==0)
                    {
                        Q.push_back(people[i]);
                        people.erase(people.begin()+i);
                        break;
                    }
                }
            
            //Recalculate & add the remaining people accordingly
                while(people.size() > 0)
                {
                    for(int i=0;i<people.size();i++)
                    {
                        if(people[i].second <= Q.size() && IsSameAsPresent(Q,people[i]))
                        {
                            Q.push_back(people[i]);
                            people.erase(people.begin()+i);
                            break;
                        }
                    }
                }
            
    
            return Q;    
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.