Reconstruct Queue Based on Height#

Suppose there is a group of people standing in a queue in a random order. Each person is represented by an integer pair (h, k), where h is the person's height, and k is the number of people in front of this person with a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The total number of people is less than 1100.

Example#

Solution#

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    // people.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    people.sort((a, b) => a[0] - b[0]);
    const n = people.length;
    let target = [];
    people.forEach((v) => {
        let spaces = v[1] + 1;
        for(let i=0;i<n;++i){
            if(target[i] === void 0 || target[i][0] === v[0]){
                spaces--;
                if(spaces <= 0 && target[i] === void 0){
                    target[i] = v;
                    break;
                }
            }
        }
    })
    return target;
};

Idea#

When each person's height is different, we sort them in ascending order of height, and then use an insertion approach to restore the queue. Initially, we assume there are n people, and then we will insert the i-th person. Now, the positions from 0 to i-1 have been arranged, no matter how they are lined up, they have no impact on the person we are about to insert. For the i-th to n-th person, as long as the insertion position is in front of the i-th person, it will affect the i-th person. Then we can establish an array of length n, and insert the sorted array one by one. When we insert the i-th person, their insertion position must be the number of people taller than them plus 1. For example, the first person to be inserted is (5, 2), then their position is <empty>, <empty>, (5, 2), which means the empty position given to them is the third position. Additionally, since they are the first number in the queue, the values after them must be greater than their own, so the values after them can be inserted based on the same rule. Here, we need to handle people with the same height specially. If the height is the same, it should also be treated as an empty position. After that, handle the position specially, if it is empty, then insert directly, otherwise insert after it. The official solution sorts the people in ascending order of height and then in descending order based on the number of people taller than them. Then we can directly apply the above rules without special handling for equal cases. For example, when we sort the array according to the above sorting rules, we get (5, 2) (5, 0) ..., then inserting (5, 2) first and then (5, 0) can achieve (5, 0), <empty>, (5, 2), which is clearly more appropriate. First, sort the array by height, and then get the length of the array n, define the target array, iterate over the sorted array, define the number of empty positions should be taken and +1, and then do n iterations. If this position is undefined or the value is the same as the one to be inserted, then reduce the number of empty positions by 1. If the number of empty positions to be inserted is less than or equal to 0 and this position is empty, then insert the value into this position and end the inner loop, and finally return the target array.

Daily Question#

Reference#