# 406. Queue Reconstruction by Height

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]]
``````

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

[[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], [6,1], [7,1], [5,0], [5,2], [4,4]]

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

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

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

``````class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});
for (int i = 1; i < people.size(); ++i) {
int cnt = 0;
for (int j = 0; j < i; ++j) {
if (cnt == people[i][1]) {
auto t = people[i];
for (int k = i - 1; k >= j; --k) {
people[k + 1] = people[k];
}
people[j] = t;
break;
}
++cnt;
}
}
return people;
}
};
``````

``````class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});
for (int i = 0; i < people.size(); i++) {
auto p = people[i];
if (p[1] != i) {
people.erase(people.begin() + i);
people.insert(people.begin() + p[1], p);
}
}
return people;
}
};
``````

Github 同步地址：

Count of Smaller Numbers After Self

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

https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89348/6-lines-Concise-C%2B%2B

https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89456/short-java-solution-without-using-extra-space

https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation