Leetcode#406. Queue Reconstruction by Height

Posted on | In |

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:

1
2
3
4
5
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]]

这道题拿到的时候就想着要先按高矮进行排序，然后再交换，后来交换的时候绕晕了，看了一眼题解。

基本思路还是先按高矮进行排序，然后用贪心算法。每次取还没有安排位置最矮的。然后从0号位数到应该安排的位置（前边是空位，或者是和当前人一样高的，在当前人之前不可能有比他高的被安排。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    
    static bool cmp(vector<int>& p1, vector<int>& p2){
        
        if(p1[0] == p2[0]) return p1[1] < p2[1];
        return p1[0] < p2[0];
        
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        
        vector<vector<int>> ans;
        int n = people.size();
        if(n == 0) return ans;
        
        vector<int> pos(n, -1);
        sort(people.begin(), people.end(), cmp);
        
        for(int i = 0; i<n; i++){
            int cnt = 0;
            int curr = people[i][0];
            for(int j = 0; j<n; j++){
                if(pos[j] == -1 && cnt == people[i][1]){
                    pos[j] = i;
                    break;
                }
                if(pos[j] == -1 || people[pos[j]][0] == curr){ //从小到大，前边不会出现比它大的
                    cnt++;
                }
            }
        }
        
        for(int i = 0; i<n; i++){
            ans.push_back(people[pos[i]]);
        }
        return ans;
        
    }
};