Not so happy with the complexity.


  • 0
    L
    class Solution {
    public:
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            multimap<int, int> mmap; // To keep the people sorted wrt their height
            vector<pair<int, int>> res(people.size(), make_pair(-1, -1)); // return value
            for (auto it = people.begin(); it != people.end(); it++) {
                mmap.insert(*it);
            }
            
            for (auto it = mmap.begin(); it != mmap.end(); it++) {
                int key = it->first;
                int val = it->second;
                int i = 0, j = 0;
                while (j <= val) {
                    // this person should have val number of people 
                    // ahead whose height are more than or equal to 
                    // this person's height. But if there is a person 
                    // whose height is smaller than this person's height, 
                    // skip incrementing the j.
                    if (res[i].first == -1 || res[i].first >= key) j++;
                    i++;
                }
                res[--i] = make_pair(key, val); // Found the place to insert this person
            }
            
            return res;
        }
    };
    

Log in to reply
 

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