LeetCode – Reconstrucción de cola por altura (Java)

Suponga que tiene una lista aleatoria de personas en una cola. Cada persona se describe mediante un par de números enteros (h, k), donde h es la altura de la persona y k es el número de personas frente a esta persona que tienen una altura mayor o igual ah. Escribe un algoritmo para reconstruir la cola.

Nota:
El número de personas es menos de 1.100.

Ejemplo

Aporte:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Producción:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Análisis

La clave para resolver este problema es encontrar el punto de partida de la reconstrucción. Para este problema, podemos comenzar a agregar el elemento más grande primero. La idea básica es seguir agregando el elemento más grande cada vez, hasta que todos los elementos estén en su lugar.

Solución Java

public int[][] reconstructQueue(int[][] people) {
    int[][] result = new int[people.length][];
    Arrays.sort(people, new Comparator<int[]>(){
        public int compare(int[] a1, int[] a2){
            if(a1[0]!=a2[0]){
                return a2[0]-a1[0];
            }else{
                return a1[1]-a2[1];
            }
        }
    });
 
    ArrayList<int[]> list = new ArrayList<int[]>();
 
    for(int i=0; i<people.length; i++){
        int[] arr = people[i];
        list.add(arr[1],arr);
    }
 
    for(int i=0; i<people.length; i++){
        result[i]=list.get(i);
    }
 
    return result;
}

La complejidad temporal de esta solución es O (n ^ 2).