题目描述

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

编写一个算法来重建这个队列。总人数少于1100人，假设输入合法。

样例

Example 1:

输入: [[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

(贪心) $O(n^2)$

思路：身高高的人只会看到比他高的人，所以当身高高的人固定好了位置，前面插入多少个矮的人都不会破坏高的人的条件限制。所以应该先决定高的人的位置，再决定矮的人的位置；高的人限制条件少，矮的人限制条件多。

1. 先按身高从大到小排序，身高一样则按照k排序：身高大或k小意味着限制条件少，应该被优先考虑。

2. 依次插入元素：由上一点，先进入res的元素不会被后进入的元素影响，因此每一次插入只需要考虑自己不需要考虑别人。当遍历到元素[a,b]的时候，比它大的元素已经进组，比它小的元素还没进组，那么它应该插到res的第b位，从而实现0到b-1的数字都比它大。

举例，输入是[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

• 排序后是[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

• 插入[7,0], res=[[7,0]]

• 插入[7,1], res=[[7,0],[7,1]]

• 插入[6,1], res=[[7,0],[6,1],[7,1]]

• 插入[5,0], res=[[5,0],[7,0],[6,1],[7,1]]

• 插入[5,2], res=[[5,0],[7,0],[5,2],[6,1],[7,1]]

• 插入[4,4], res=[[5,0],[7,0],[5,2],[4,4],[6,1],[7,1]]

• 最终答案是[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

C++ 代码

class Solution {
public:

  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    auto cmp = [](const vector<int> &a, const vector<int> &b) {
            return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
        };
    sort(people.begin(), people.end(), cmp);
    vector<vector<int>> res;
    for(auto p:people) res.insert(res.begin()+p[1],p);
    return res;
  }
};