Queue Reconstruction by Height

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]]

This problem actually uses the easiest insert sort algorithm. We first sort the array with higher height and fewer people in the front:

[7,0] [7,1] [6,1][5,0][5,2][4,4]



Then we insert the array to correct index:

[7, 0][6,1][7, 1][5,0][5,2][4,4]

[5,0][7, 0][6,1][7, 1][5,2][4,4]

[5,0][7, 0][6,1][5,2][7, 1][4,4]

[5,0][7, 0][6,1][5,2][4,4][7, 1]


That's it.

public int[][] reconstructQueue(int[][] people) {
        if (people.length <= 1) {
            return people;
        }
        
        Arrays.sort(people, new Comparator<int[]>() {
           @Override
           public int compare(int[] first, int[] second) {
               if (first[0] != second[0]) {
                   return second[0] - first[0];
               } else {
                   return first[1] - second[1];
               }
           }
        });
        
        int len = people.length;
        for (int j = 1; j < len; j++) {
            int count = 0;
            int[] curr = people[j];
            for (int i = 0; i < j; i++) {
                if (count == curr[1]) {
                    for (int k = j - 1; k >= i; k--) {
                        people[k + 1] = people[k];
                    }
                    people[i] = curr;
                    break;
                } else {
                    if (people[i][0] >= people[j][0]) {
                        count++;
                    }
                }
            }
        }
        return people;
    }