406. Queue Reconstruction by Height
排序后插入 Time = O(n^2), space = O(n)
input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 1) 按照高度从大到小排序，相同的高度按照位置从小到大排序：[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]] 2) For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
Arraylist add API: public void add(int index, E element): Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>(){
@Override
public int compare(int[] p1, int[] p2) {
if (p1[0] != p2[0]) {
return p2[0] - p1[0];
} else {
return p1[1] - p2[1];
}
}
}); // sort
List<int[]> tmp = new ArrayList<>();
for (int i = 0; i < people.length; i++) {
tmp.add(people[i][1], people[i]);
} // insert one by one
int[][] res = new int[people.length][2];
for (int i = 0; i < people.length; i++) {
res[i] = tmp.get(i);
} // comvert to 2d-array
return res;
}
}