Leetcode June Challenge - Day 6

Problem: LeetCode June Challenge - Day 6

Ideas:

  1. People with the same height will be sorted according to the number of people in front of them.
  2. Let’s say we have a person X, and a list with every person who is higher or has the same height but has less people in front of them. It is quite obvious that the position of X in that list will be X[1], and everything we insert afterwars won’t matter, since people who are shorter are irrelevant to X, and people with the same height but more people in front of them will be places behind X.

Solution:

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        int n = people.size();
        if(n == 0) return people;
        
        auto cmp = [] (vector<int>& a, vector<int> b) -> bool {
            return (a[0] > b[0]) || (a[0] == b[0] && a[1] < b[1]);
        };
        sort(people.begin(), people.end(), cmp);
        
        for(int i=0; i<n; ++i)
            // place people[i] at people[i][1]
            for(int j = people[i][1]; j<i; ++j)
                swap(people[i], people[j]);
        
        return people;
    }
};