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 ascending instead.
   */
  public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (p1, p2) -> p2[0] - p1[0] == 0 ? p1[1] - p2[1] : p2[0] - p1[0]);
    final List<int[]> res = new ArrayList<>(people.length);
    for (int[] p : people) {
      res.add(p[1], p);
    }
    return res.toArray(new int[0][0]);
  }

  /**
   * Same idea.
   * But comparator is faster than lambda in execution.
   */
  public int[][] reconstructQueue2(int[][] people) {
    Arrays.sort(people, new Comparator<int[]>() {
      @Override
      public int compare(int[] person1, int[] person2) {
        return person2[0] - person1[0] == 0 ? person1[1] - person2[1] : person2[0] - person1[0];
      }
    });
    final List<int[]> res = new ArrayList<>(people.length);
    for (int[] p : people) {
      res.add(p[1], p);
    }
    return res.toArray(new int[0][0]);
  }
}

@@ -814,165 +814,315 @@
   * 
-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
+Greedy.%0A   * Assuming there's always a solution.To fit the requirements:%0A   * People have smaller height should go to the tail as much as possible.%0A   * People have larger k should go to the front as much as possible.%0A   * %3Cp%3E%0A   * Sort the array by height descending and k ascending.%0A   * Insert the person
  to 
@@ -1423,27 +1423,42 @@
 , (p
-1, p
+erson1, person
 2) -%3E p
+erson
 2%5B0%5D - p
 1%5B0%5D
@@ -1449,24 +1449,29 @@
 rson2%5B0%5D - p
+erson
 1%5B0%5D == 0 ? 
@@ -1471,24 +1471,29 @@
 == 0 ? p
+erson
 1%5B1%5D - p
 2%5B1%5D : p
@@ -1484,24 +1484,29 @@
 1%5B1%5D - p
+erson
 2%5B1%5D : p
 2%5B0%5D - p
@@ -1497,24 +1497,29 @@
 2%5B1%5D : p
+erson
 2%5B0%5D - p
 1%5B0%5D);%0A 
@@ -1510,16 +1510,21 @@
 2%5B0%5D - p
+erson
 1%5B0%5D);%0A 
@@ -1888,16 +1888,16 @@
 verride%0A
-
       pu
@@ -1941,24 +1941,68 @@
  person2) %7B%0A
+        // Sort based on height desc, k asc%0A
         retu

update 406 Queue Reconstruct By Height