Simple commented Java solution using Priority Queue


  • 3
    /*
    This sounds like a priority queue question since we are organizing
    items based come metrics.
    But looks like we have 2 metrics here, i.e we need to take both h and k into consideration
    
    First we sort all the people based on h, in descending order.
    Then we do insertion sort based on k
    */
    
    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            int[][] result = new int[people.length][];
            List<int[]> list = new ArrayList<int[]>();
            /*use a pq to sort all the people based on h*/
            PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new listComparator());
            for(int i = 0; i < people.length; i++){
                queue.offer(people[i]);
            }
            /*insertion sort based on k*/
            while(queue.size() != 0){
                insert(list, queue.poll());
            }
            for(int i = 0; i < people.length; i++){
                result[i] = list.get(i);
            }
            return result;
        }
        
        /*insertion sort based on k*/
        private void insert(List<int[]> list, int[] element){
            if(list.size() == 0) {
                list.add(element);
                return;
            }
            int count = 0;
            for(int i = 0; i < list.size(); i++){
                if(count == element[1]){
                    list.add(i, element);
                    return;
                }else if(list.get(i)[0] >= element[0]){
                    count++;
                }
            }
            list.add(element);
        }
        
        /*pq comparator class*/
        class listComparator implements Comparator<int[]>{
            public int compare(int[] first, int[] second){
                if(first[0] != second[0])  return second[0] - first[0];
                else return first[1] - second[1];
            }
        }
    }````

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.