G8 - Queue Reconstruction by Height

May 24, 2017

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 :
Sort the array by decreasing order of heights and increasing order of taller people if heights are same. iterate in the array and position each element at the index representated by taller people in front.

                
public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if(people == null || people.length == 0)
            return new int[0][0];

        Arrays.sort(people, new Comparator(){
            public int compare(int[] o1, int[] o2){
                return o1[0] != o2[0] ? o2[0] - o1[0] : o1[1] - o2[1];
            }
            });

            List res = new LinkedList<>();
            for(int[] cur : people){
                res.add(cur[1], cur);
            }
            return res.toArray(new int[people.length][]);
    }
}