package com.freetymekiyan.algorithms.level.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 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.
 * <p>
 * Note:
 * The number of people is less than 1,100.
 * <p>
 * Example
 * <p>
 * Input:
 * [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
 * <p>
 * Output:
 * [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
 * <p>
 * Tags: Greedy
 * Similar Problems: (H) Count of Smaller Numbers After Self
 */
public class QueueReconstructionByHeight {

    /**
     * Sort the array by height descending and k ascending.
     * Pick the highest people from the array.
     * Then pick the second highest from the array and insert to result according to k.
     * Repeat till there is no more people.
     * <p>
     * If k means the # of people in front of him that are shorter or equal.
     * We should sort by height ascending and k asceding instead.
     */
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0] == 0 ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        });
        List<int[]> res = new ArrayList<>();
        for (int[] p : people) {
            res.add(p[1], p);
        }

        return res.toArray(new int[0][0]);
    }

}

@@ -803,18 +803,14 @@
  %7B%0A%0A
-  
   /**%0A
-  
    *
@@ -866,18 +866,16 @@
 ing.%0A   
- 
- 
 * Pick t
@@ -908,18 +908,16 @@
  array.%0A
-  
    * The
@@ -997,18 +997,16 @@
 o k.%0A   
- 
- 
 * Repeat
@@ -1039,18 +1039,16 @@
 ple.%0A   
-  
 * %3Cp%3E%0A  
@@ -1048,18 +1048,16 @@
  %3Cp%3E%0A   
- 
- 
 * If k m
@@ -1123,18 +1123,16 @@
 ual.%0A   
-  
 * We sho
@@ -1170,16 +1170,17 @@
 d k asce
+n
 ding ins
@@ -1192,15 +1192,11 @@
 %0A   
-  
 */%0A
-  
   pu
@@ -1243,24 +1243,409 @@
 ople) %7B%0A    
+Arrays.sort(people, (p1, p2) -%3E p2%5B0%5D - p1%5B0%5D == 0 ? p1%5B1%5D - p2%5B1%5D : p2%5B0%5D - p1%5B0%5D);%0A    final List%3Cint%5B%5D%3E res = new ArrayList%3C%3E(people.length);%0A    for (int%5B%5D p : people) %7B%0A      res.add(p%5B1%5D, p);%0A    %7D%0A    return res.toArray(new int%5B0%5D%5B0%5D);%0A  %7D%0A%0A  /**%0A   * Same idea.%0A   * But comparator is faster than lambda in execution.%0A   */%0A  public int%5B%5D%5B%5D reconstructQueue2(int%5B%5D%5B%5D people) %7B%0A
     Arrays.s
@@ -1678,30 +1678,24 @@
 %3Cint%5B%5D%3E() %7B%0A
-      
       @Overr
@@ -1698,22 +1698,16 @@
 verride%0A
-      
       pu
@@ -1729,17 +1729,22 @@
 e(int%5B%5D 
-o
+person
 1, int%5B%5D
@@ -1748,22 +1748,19 @@
 t%5B%5D 
-o2) %7B%0A        
+person2) %7B%0A
     
@@ -1770,25 +1770,35 @@
  return 
-o
+person
 2%5B0%5D - 
-o
+person
 1%5B0%5D == 
@@ -1805,33 +1805,53 @@
 0 ? 
-o
+person
 1%5B1%5D - 
-o
+person
 2%5B1%5D : 
-o
+person
 2%5B0%5D - 
-o
+person
 1%5B0%5D
@@ -1862,20 +1862,10 @@
     
-     
- 
 %7D%0A
-    
     
@@ -1872,19 +1872,21 @@
 %7D);%0A    
-   
+final
  List%3Cin
@@ -1912,23 +1912,32 @@
 yList%3C%3E(
-);%0A    
+people.length);%0A
     for 
@@ -1963,22 +1963,16 @@
 %7B%0A      
-  
-    
 res.add(
@@ -1989,19 +1989,10 @@
     
-    %7D%0A%0A    
+%7D%0A
     
@@ -2028,15 +2028,12 @@
 %5B0%5D);%0A  
-  %7D%0A
+%7D
 %0A%7D%0A

update 406 Queue Reconstruction by Height