# 406. Queue Reconstruction by Height 根据身高重建队列

@TOC

## # 题目描述

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example：

``````Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
``````

## # 解题方法

``````[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
``````

``````[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
``````

Python代码如下：

``````class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
people.sort(key = lambda x : (-x[0], x[1]))
res = []
for p in people:
res.insert(p[1], p)
return res
``````

C++代码如下，需要注意自定义sort()函数的比较方法。

``````class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(), [](const pair<int, int> a, const pair<int, int> b) {
return (a.first > b.first) || (a.first == b.first && a.second < b.second);
});
vector<pair<int, int>> res;
for (auto p : people) {
res.insert(res.begin() + p.second, p);
}
return res;
}
};
``````

Java代码如下，之前写的，有点冗长了。

``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0) {
return people;
}
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] p1, int[] p2) {
return p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0];
}
});
List<int[]> temp = new ArrayList<int[]>();
for (int[] aPeople : people) {
if (people.length == aPeople[1]) {
} else {
}
}
int ans[][] = new int[people.length][2];
for (int i = 0; i < temp.size(); i++) {
ans[i] = temp.get(i);
}
return ans;
}
}
``````

## # 日期

2017 年 3 月 30 日 2018 年 12 月 6 日 —— 周四啦！