https://leetcode-cn.com/problems/queue-reconstruction-by-height/

难度：中等

---

  假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：

  总人数少于1100人。

示例

输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

---

解法1：排序+调整

  通过观察，我们可以知道，对于一组数据，如示例中的 (7,0) 和 (7,1)，无论它们所处的位置在哪，在最终结果中，它们的相对位置是不会发生变化的：(7,1) 一定会在 (7,0) 的后面，可能中间隔了一个、可能隔了 n 个。

  因此，我们可以先对这组数据排序，先保证它们的相对位置，具体做法是根据 (h, k) 来排序：我们先按 h 从大到小进行排序，这样保证了对于每一个数 i，它前面的数字都不会小于自身，然后对于 h 相同的数字，按 k 从小到大排序，这样，对于 h 相同的数据，它们的相对位置开始就是正确的。

  之后，遍历这组排序过的数据，我们使用 tuple 来表示一个 (h, k) 对，遍历过程中，数组索引 i 能够表示不小于当前 tuple 的所有 tuple 的个数（因为我们提前按 h 进行排序了），这样，我们只要根据每个 tuple 的 k 来进行调整即可。

  具体调整方法是：对于当前的 tuple ，若 k < i ，说明在当前 tuple 前面的位置，比它高的 tuple 个数太多了，需要将这个 tuple 向前调整 i-k 个位置，让其前面的 tuple 个数刚好等于 k，也就是移动到第 k 个位置。且这样调整并不会影响到已调整的序列，因为那些数据的相对位置并不会发生改变。

JS 代码：

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    if (people.length < 2) {
        return people;
    }

    let res = [];
    
    // 先根据 h 和 k 排序，主 h 副 k , h 从大到小排序，k 从小到大排序
    people.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        }
        return b[0] - a[0];
    });

    for (let i = 0; i < people.length; i++) {
        let k = people[i][1];
        if (k < i) {
            res.splice(k, 0, people[i]);
        } else {
            res[i] = people[i];
        }
    }

    return res;
};

解法2：逐个插入、调整

（第 27/37 个 case 会超时）

  主要思路是先找到序列的第一个 tuple ，然后根据每个 tuple 的 h 和 k 找到插入的位置，所有数据都插入完成之后，有些 tuple 会因为插入操作而导致站位错误，因此需要逐个检查判断是否站错，若站错，则将这个 tuple 重新插入，反复执行此操作，直到所有数据都满足站位要求：

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    if (people.length < 2) {
        return people;
    }
    let res = [];
    let n = people.length;
    let first;
    let tuple, k, height, insertIndex;
    
    // 先进行第一次排序
    for (let i = 0; i < n; i++) {
        tuple = people[i];
        k = tuple[1];
        height = tuple[0];
        insertIndex = 0;
        if (k === 0) {
            while(insertIndex < res.length && res[insertIndex][0] < height) {
                insertIndex++;
            }
            res.splice(insertIndex, 0, tuple);
        } else {
            while(insertIndex < res.length && k > 0) {
                if (res[insertIndex++][0] >= height) {
                    k--;
                }
            }
            res.splice(insertIndex, 0, tuple);
        }
    }

    let flag = true;
    while(flag) {
        flag = false;
        for (let i = 0; i < n; i++) {
            tuple = res[i];
            k = tuple[1];
            height = tuple[0];
            if (k !== 0) {
                // 遍历当前 tuple 前面的人，看是否满足 k 的要求
                for (let j = 0; j < i; j++) {
                    let tuple1 = res[j];
                    if (tuple1[0] >= height) {
                        k--;
                    }
                }
                if (k !== 0) {
                    k = tuple[1]; // k 要重新赋值，用于下面的重新插入
                    res.splice(i, 1); // 将错误的 tuple 从结果中移除
                    flag = true; // 需要再次判断
                    break;
                }
            }
        }
        // 若存在错误的站位，则重新插入，且 k 、height 和 tuple 可以就使用之前的
        if (flag) {
            insertIndex = 0;
            while(insertIndex < n-1 && k > 0) {
                if (res[insertIndex++][0] >= height) {
                    k--;
                }
            }
            res.splice(insertIndex, 0, tuple);
        }
    }

    return res;
};