【leetcode】406. Queue Reconstruction by Height

妖狐艹你老母 2022-07-03 20:22 95阅读 0赞

# 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\]\]

**题意** ：给定一个随机的序列，序列里面的每个元素都是一个整数对(h,k), 其中h表示当前这个人的身高，k表示这个人前面有k个人的身高不小于这个人。要求重新排列序列，使得其满足这个要求。

我们可以将这个大问题先拆分成小问题：给定的这个随机序列里面的人身高都相同，重拍序列以满足条件。比如给定序列\[\[7,3\], \[7,1\], \[7,0\], \[7,2\]\]，那么显然，我们可以通过将整数对插入到k个位置，就能得到满足条件的序列： \[\[7,0\], \[7,1\], \[7,2\], \[7,3\]\]。同样的，给定另外一些矮一点的人，由于比他们高的人都已经排好了，那么只需要将这些矮的人也插入到对应的第k个位置就行了。比如给定\[6,1\], 那么说明这个人前面有两个身高为7的人，则插入\[6,1\]得到 \[\[7,0\], \[6,1\], \[7,1\], \[7,2\], \[7,3\]\]。接着给定\[6,3\]，那么说明这个人前面有两个身高为7或者6的人，插入\[6,3\]得到 \[\[7,0\], \[6,1\], \[7,1\], \[6,3\], \[7,2\], \[7,3\]\]。

class Solution {
    public:
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            vector<pair<int, int>> result;
            if (people.size() == 0) return result;
    
            auto cmp = [](const pair<int, int> &a, const pair<int, int> &b) {
                // sort height by descent order and number by ascent order
                return (a.first > b.first || (a.first == b.first && a.second < b.second));
            };
            sort(people.begin(), people.end(), cmp);
    
            for (auto p : people) {
                result.insert(result.begin() + p.second, p);
            }
            return result;
        }
    };
    
    总结：c++11大法好~