Welcome to Subscribe On Youtube
406. 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] = [h_{i}, k_{i}]
represents the i^{th}
person of height h_{i}
with exactly k_{i}
other people in front who have a height greater than or equal to h_{i}
.
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] = [h_{j}, k_{j}]
is the attributes of the j^{th}
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]]
Constraints:
1 <= people.length <= 2000
0 <= h_{i} <= 10^{6}
0 <= k_{i} < people.length
 It is guaranteed that the queue can be reconstructed.
Solutions

class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (a, b) > a[0] == b[0] ? a[1]  b[1] : b[0]  a[0]); List<int[]> ans = new ArrayList<>(people.length); for (int[] p : people) { ans.add(p[1], p); } return ans.toArray(new int[ans.size()][]); } }

class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] > b[0]  (a[0] == b[0] && a[1] < b[1]); }); vector<vector<int>> ans; for (const vector<int>& p : people) ans.insert(ans.begin() + p[1], p); return ans; } };

class Solution: def reconstructQueue(self, people: List[List[int]]) > List[List[int]]: people.sort(key=lambda x: (x[0], x[1])) ans = [] for p in people: ans.insert(p[1], p) return ans

func reconstructQueue(people [][]int) [][]int { sort.Slice(people, func(i, j int) bool { a, b := people[i], people[j] return a[0] > b[0]  a[0] == b[0] && a[1] < b[1] }) var ans [][]int for _, p := range people { i := p[1] ans = append(ans[:i], append([][]int{p}, ans[i:]...)...) } return ans }