原题链接在这里：https://leetcode.com/problems/queue-reconstruction-by-height/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]]
题解：
先把最高的人挑出来，然后按照k把他们插入到ArrayList<int []> resList中. 然后再插第二高的，以此类推.
Time Complexity: O(nlogn). n = people.length. sort用时O(nlogn), 插入时因为使用ArrayList, 可以忽略resize的用时, 所以插入共用时O(n).
Space: O(n).
AC Java:
1 class Solution { 2 public int[][] reconstructQueue(int[][] people) { 3 if(people == null || people.length == 0|| people[0].length != 2){ 4 return people; 5 } 6 7 Arrays.sort(people, new Comparator<int []>(){ 8 public int compare(int [] a, int [] b){ 9 if(a[0] == b[0]){ 10 return a[1]-b[1]; 11 } 12 return b[0]-a[0]; 13 } 14 }); 15 16 ArrayList<int []> resList = new ArrayList<int []>(); 17 for(int [] item : people){ 18 resList.add(item[1], item); 19 } 20 21 return resList.toArray(new int[people.length][2]); 22 } 23 }
LeetCode Queue Reconstruction by Height
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/7568309.html