LeetCode 406.

406.根据身高重建队列

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中 h 是这个人的身高,k是应该排在这个人前面且身高大于或等于h的人数。 例如：[5,2] 表示前面应该有2个身高大于等于5的人，而 [5,0] 表示前面不应该存在身高大于等于5的人。

编写一个算法，根据每个人的身高h重建这个队列，使之满足每个整数对(h, k)中对人数k的要求。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 很简单的一个思路：
  1.先对队列按照身高降序排列，k升序排列，这样就得到了一个排序后的队列，如：
  [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]--->[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
  排序后的队列的特点是：对于每一组数对做插入操作，都不会影响k值的正确性。
  2.遍历这个队列，若当前数对的k值不等于它的序号，那么将它插入到k值对应的序号处。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        insertionSort(people);
        reconstructSort(people);
        return people;
    }
    void insertionSort(vector<vector<int>>& people){
        int n = people.size();
        for(int i=1;i<=n-1;i++){
            vector<int> temp;
            temp.push_back(people[i][0]);
            temp.push_back(people[i][1]);
            int j;
            for(j=i-1;j>=0;j--){
                if(people[j][0]<=temp[0]){
                    if(people[j][0]<temp[0]){
                        people[j+1][0] = people[j][0];
                        people[j+1][1] = people[j][1];
                    }
                    else if(people[j][0]==temp[0]){
                        if(people[j][1]>temp[1]){
                            people[j+1][0] = people[j][0];
                            people[j+1][1] = people[j][1];
                        }
                        else break;
                    }
                }
                else break;
            }
            people[j+1][0] = temp[0];
            people[j+1][1] = temp[1];
        }
    }
    void reconstructSort(vector<vector<int>>& people){
        int i,j;
        for(i=0;i<=people.size()-1;i++){
            if(people[i][1]<i){
                vector<int> temp;
                temp.push_back(people[i][0]);
                temp.push_back(people[i][1]);
                for(j=i;j>=temp[1]+1;j--){
                    people[j][0] = people[j-1][0];
                    people[j][1] = people[j-1][1];
                }
                people[j][0] = temp[0];
                people[j][1] = temp[1];
            }
        }
    }
};