@@ -0,0 +1,1670 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.Comparator;%0Aimport java.util.List;%0A%0A/**%0A * Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k),%0A * 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%0A * than or equal to h. Write an algorithm to reconstruct the queue.%0A * %3Cp%3E%0A * Note:%0A * The number of people is less than 1,100.%0A * %3Cp%3E%0A * Example%0A * %3Cp%3E%0A * Input:%0A * %5B%5B7,0%5D, %5B4,4%5D, %5B7,1%5D, %5B5,0%5D, %5B6,1%5D, %5B5,2%5D%5D%0A * %3Cp%3E%0A * Output:%0A * %5B%5B5,0%5D, %5B7,0%5D, %5B5,2%5D, %5B6,1%5D, %5B4,4%5D, %5B7,1%5D%5D%0A * %3Cp%3E%0A * Tags: Greedy%0A * Similar Problems: (H) Count of Smaller Numbers After Self%0A */%0Apublic class QueueReconstructionByHeight %7B%0A%0A    /**%0A     * Sort the array by height descending and k ascending.%0A     * Pick the highest people from the array.%0A     * Then pick the second highest from the array and insert to result according to k.%0A     * Repeat till there is no more people.%0A     * %3Cp%3E%0A     * If k means the # of people in front of him that are shorter or equal.%0A     * We should sort by height ascending and k asceding instead.%0A     */%0A    public int%5B%5D%5B%5D reconstructQueue(int%5B%5D%5B%5D people) %7B%0A        Arrays.sort(people, new Comparator%3Cint%5B%5D%3E() %7B%0A            @Override%0A            public int compare(int%5B%5D o1, int%5B%5D o2) %7B%0A                return o2%5B0%5D - o1%5B0%5D == 0 ? o1%5B1%5D - o2%5B1%5D : o2%5B0%5D - o1%5B0%5D;%0A            %7D%0A        %7D);%0A        List%3Cint%5B%5D%3E res = new ArrayList%3C%3E();%0A        for (int%5B%5D p : people) %7B%0A            res.add(p%5B1%5D, p);%0A        %7D%0A%0A        return res.toArray(new int%5B0%5D%5B0%5D);%0A    %7D%0A%0A%7D%0A

add Queue Reconstruction By Height