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]]
先按h从大到小排序，h相同的按k从小到大排序， [[7,0], [[7,1]], [6,1], [5,0], [5,2], [4,4]] 然后遍历整个数据结构，将其中的元素插入到第k个位置。 class Solution { public: void swap(vector<pair<int, int>>& people,int a ,int b){ int tmp1=people[a].first; int tmp2=people[a].second; people[a].first=people[b].first; people[a].second=people[b].second; people[b].first=tmp1; people[b].second=tmp2; } vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) { int len=people.size(); for(int i=0;i<len-1;i++){ for(int j=i+1;j<len;j++){ if(people[i].first<people[j].first) swap(people,i,j); else if(people[i].first == people[j].first && people[i].second > people[j].second) swap(people,i,j); } } vector<int> height,count; for(int i=0;i<len;i++){ height.insert(height.begin()+people[i].second,people[i].first); count.insert(count.begin()+people[i].second,people[i].second); } for(int i=0;i<len;i++){ people[i].first=height[i]; people[i].second=count[i]; } return people; } };
