Difficulty: Medium
Problem Link: https://leetcode.com/problems/queue-reconstruction-by-height/
Problem
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]]
Tag: Greedy
Explanation
- 這道題目的關(guān)鍵是：只有身高大于等于自身的人佛吓，對(duì)于K值才有影響宵晚。假設(shè)A的身高為h，身高大于等于h的人的站位會(huì)影響A的K值维雇，而身高小于h的人無(wú)論是站在A的前面抑或是后面淤刃，對(duì)于A的K值都是沒有影響的。但是A的站位卻會(huì)影響比A身高矮的人的K值吱型，所以唯有先確定A的站位逸贾，才可確定身高小于A的人的站位，所以初步猜想是將所有人按照身高從高到低排序，依次插入到一個(gè)新的隊(duì)列中去铝侵，插入的位置就是K值的大小灼伤。
- 第二個(gè)要考慮的問(wèn)題就是身高相同的人，但是K值不同咪鲜，顯然K值越大的人站位越靠后狐赡，因?yàn)閷?duì)于H相同的人，站位靠后的K值至少比前面的大1疟丙。所以要先插入K值較小的人颖侄。因此得出這樣的排序規(guī)則。
auto comp = [](const pair<int, int>& x, const pair<int, int>& y) { return (x.first > y.first || (x.first == y.first && x.second < y.second)); };
cpp solution
class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
auto comp = [](const pair<int, int>& x, const pair<int, int>& y) {
return (x.first > y.first || (x.first == y.first && x.second < y.second));
};
sort(people.begin(), people.end(), comp);
vector<pair<int, int>> res;
for (auto &p : people) {
res.insert(res.begin() + p.second, p);
}
return res;
}
};
