Level
Medium
Description
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]] ```
Solution
First sort the array people
in the following order. Suppose person1
and person2
are two elements of people
, then person1
is before person2
if and only if person1[0] > person2[0]
or person1[0] == person2[0]
and person1[1] < person2[1]
. That is, sort the people according to height in descending order. If two people have the same height, sort them according to count in ascending order.
Next use the idea of insertion sort to reconstruct the array. For index i
from 1 to people.length  1
, people[i]
’s height must be less than or equal to all the people in the index range from 0 to i  1
. Suppose count = people[i][1]
. If count < i
, then insert people[i]
at index count
.
Take the example in the problem. The array is reconstructed in the following way.
The input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]].
After sorting: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]].
First insertion: [7,1] is at the correct index, so do not change.
Second insertion: Insert [6,1] at index 1. The array becomes [[7,0], [6,1], [7,1], [5,0], [5,2], [4,4]].
Third insertion: Insert [5,0] at index 0. The array becomes [[5,0], [7,0], [6,1], [7,1], [5,2], [4,4]].
Fourth insertion: Insert [5,2] at index 2. The array becomes [[5,0], [7,0], [5,2], [6,1], [7,1], [4,4]].
Fifth insertion: Insert [4,4] at index 4. The array becomes [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].
And the reconstructed array is [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].
Java

class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, new Comparator<int[]>() { public int compare(int[] person1, int[] person2) { if (person1[0] != person2[0]) return person2[0]  person1[0]; else return person1[1]  person2[1]; } }); int length = people.length; for (int i = 1; i < length; i++) { int[] person = people[i]; int height = person[0], count = person[1]; if (count < i) { for (int j = i  1; j >= count; j) { for (int k = 0; k < 2; k++) people[j + 1][k] = people[j][k]; } people[count][0] = height; people[count][1] = count; } } return people; } } public class Queue_Reconstruction_by_Height { /* Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value. For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth. E.g. input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] subarray after step 1: [[7,0], [7,1]] subarray after step 2: [[7,0], [6,1], [7,1]] */ class Solution { public int[][] reconstructQueue(int[][] people) { // maxheap to hold list of people in comparison with height and then use k to order the same height people PriorityQueue<int[]> pq = new PriorityQueue<>( (o1, o2) > o1[0] == o2[0] ? o1[1]  o2[1] : o2[0]  o1[0] ); for (int[] each: people) { pq.offer(each); } // now pq is: [[7,0], [7,1], [6,1], [5,0], [5,2]], [4,4] List<int[]> result = new ArrayList<>(); // [[7,0], // [[7,0], [7,1], // [[7,0], [6,1], [7,1]] while (!pq.isEmpty()) { int[] each = pq.poll(); result.add(each[1], each); } return result.toArray(people); } } }

// OJ: https://leetcode.com/problems/queuereconstructionbyheight // Time: O(N^2) // Space: O(1) // Ref: https://discuss.leetcode.com/topic/60470/6linesconcisec class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort(people.begin(), people.end(), [](vector<int> &a, vector<int> &b) { return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0]; }); vector<vector<int>> ans; for (auto &p : people) ans.insert(ans.begin() + p[1], p); return ans; } };

class Solution(object): def reconstructQueue(self, people): """ :type people: List[List[int]] :rtype: List[List[int]] """ queue = [] for p in sorted(people, key=lambda (h, k): (h, k)): queue.insert(p[1], p) return queue