Java O(n^2) greedy solution


  • 5
    D

    We always choose the current shortest height (so we need to sort input first), and then try to put it into the right position. We simply scan from the left and count how many persons are really >= its own height. Then we put the person into the empty slot.

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            if (people == null || people.length <= 1) {
                return people;
            }
            Arrays.sort(people, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
                }
            });
            int n = people.length;
            int[][] ret = new int[n][];
            for (int i = 0; i < n; i++) {
                for (int j = 0, ahead = 0; j < n; j++) {
                    if (ahead < people[i][1]) {
                        ahead += (ret[j] == null || ret[j][0] >= people[i][0]) ? 1 : 0;
                    } else if (ret[j] == null) {
                        ret[j] = people[i];
                        break;
                    }
                }
            }
            return ret;
        }
    }
    

  • 0
    Z

    Thanks for the code! Here is my C++. I did one pass for people with the same height.

    class Solution {
    public:
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            sort(people.begin(), people.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.first < b.first || (a.first == b.first && a.second < b.second);});
            int n = people.size();
            vector<pair<int, int>> ans(n, {-1, 0});
            for (int i = 0; i < n;) {
                int k = people[i].first, j = 0, ahead = 0;
                while (i < n && people[i].first == k) {
                    while (ahead < people[i].second) {
                        if (ans[j++].first == -1) ahead++;
                    }
                    while (ans[j].first != -1) j++;
                    ans[j++] = people[i++];
                    ahead++;
                }
            }
            return ans;
            // Another solution to choose highest people first
            /*sort(people.begin(), people.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second < b.second || (a.second == b.second && a.first < b.first);});
            int n = people.size();
            vector<pair<int, int>> ans;
            for (int i = 0; i < n; i++) {
                ans.insert(ans.begin()+people[i].second, people[i]);
            }
            return ans;*/
        }
    };
    

  • 0

    To relieve the pain for future readers:
    this solution sort in the manner of height ascending first, and rank ascending if height tie (rank as defined as number of people taller than or equal to my height who is also standing before me).

    After sorting, we iterate through people, for each people[i], we try to directly put it into the correct position. j is used to iterate from left to right in the output list, while ahead is used to record the actual number of slots that could be counted into the calculation of people[i]'s rank. If at position j we already have somebody placed, and also this somebody is shorter than people[i] (which is yet to be placed in this iteration of the outer loop), then we don't count this slot into ahead since people[i]'s rank's calculation does not take this slot's person into account anyway(he's shorter).

    When ahead reaches people[i]'s rank, put him there.

    Come on people, at least tell the readers what your variable name means.


Log in to reply
 

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