###### tags: `Leetcode` `medium` `greedy` `sort` `python` `c++`

# 406. Queue Reconstruction by Height

## [題目連結:] https://leetcode.com/problems/queue-reconstruction-by-height/description/

## 題目:
You are given an array of people, ```people```, which are the attributes of some people in a queue (not necessarily in order). Each ```people[i] = [hi, ki]``` represents the ```ith``` person of height ```hi``` with **exactly** ```ki``` other people in front who have a height greater than or equal to ```hi```.

Reconstruct and return the queue that is represented by the input array people. The returned ```queue``` should be formatted as an array queue, where ```queue[j] = [hj, kj]``` is the attributes of the ```jth``` person in the queue (```queue[0]``` is the person at the front of the queue).

**Example 1:**

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

**Example 2:**

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

## 解題想法:
* 此題為給一數組people:
* people[i]=[hi,ki]
* hi: 身高
* ki: 由左到右有多少人高於自己
* 將數組排序好
* Greedy+Sort
* **Step1**:
* 先按照hi由大排到小
* **Step2**:
* 再由ki小到大: 處理對於相同hi之ki問題
* **Step3**:
* 最後將每人依照**ki**插入對應位置

## Python:
* 排序使用好工具lambda

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(key=lambda x: (-x[0],x[1])) 
        #-x[0]表示看hi由大到小 x[1]表示看ki由小到大
        res=[]
        for p in people:
            res.insert(p[1],p) #list.insert(index,obj)
        return res
    
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
result=Solution()
ans=result.reconstructQueue(people)
print(ans)

## C++:
* c++ sort排序技巧可參考 https://shengyu7697.github.io/std-sort/

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //sort vector use lambda function
        sort(people.begin(), people.end(), [](vector<int>& x, vector<int>& y){
            // 0: hi, 1: ki
            return x[0]>y[0] || (x[0]==y[0] && x[1]<y[1]);
        });
        vector<vector<int>> res;
        for (auto& val: people){
            res.insert(res.begin()+val[1],val);
        }
        return res;
    }
};