梨花院落溶溶月
柳絮池塘淡淡风
C++，排序模拟题，贪心思想。
要解这道题，首先明白一个事，就是对于该序列，身高最低的人在剩余空位中的位置是可以直接确定的。
比如序列：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]，元素[4,4]在新序列的是可以直接确定的，因为它就是身高最矮的，就是新序列中的4号位；同理[5,2]也是能确定的，是在2号位，[5,0]是在0号位；而[6,1]是在剩余空位中的1号位，也就是3号位。
所以我们要做的，就是不断找到这个身高最低的人，然后确定在剩余空位中的位置再进行插入，所以是两个步骤。
- 排序，按照身高从低到高，身高相同，则按照位置从大到小
- 在剩余序列中插入到对应的位置
以上述思路为基础，写出代码：
class Solution {
public:
static bool cmp(vector<int> &a, vector<int> &b) {
if (a[0] == b[0])
return a[1] > b[1];
else
return a[0] < b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<int> init = {-1, 0};
vector<vector<int>> ans(people.size(), init);
for (const auto &it : people) {
vector<int> tit = it;
for (int i = 0; i < ans.size(); i++) {
if (ans[i] == init && tit[1]-- == 0)
ans[i] = it;
}
}
return ans;
}
};
