filas permutar de una matriz para eliminar subsecuencias crecientes

Question

El siguiente problema es tomada de Problems on Algorithms (Problema 653):

se le da una matriz de n x 2 de números. Encuentre un algoritmo O (n log n) que permute las filas en la matriz de modo que ninguna columna de la matriz contenga una subsecuencia creciente (que puede no consistir en elementos de la matriz contigua) más larga que ⌈ √ n. ⌉

No estoy seguro de cómo solucionar esto. Creo que podría usar algún tipo de recurrencia de divide y vencerás, pero parece que no puedo encontrar ninguna.

¿Alguien tiene alguna idea de cómo solucionar esto?

Answer 1

Heres es mi solución.

1) Ordene las filas según el primer elemento, de mayor a menor.

1 6 5 1 
3 3 -\ 3 3 
2 4 -/ 2 4 
5 1 1 6 

2) Dividir en grupos de ⌈√n⌉, y lo que queda (no más de grupos ⌈√n⌉)

5 1 5 1 
3 3 -\ 3 3 
2 4 -/ 
1 6 2 4 
     1 6 

3) Clasificar filas en cada grupo de acuerdo con la segundo elemento de mayor a menor

5 1 3 3 
3 3 5 1 
    -> 
2 4 1 6 
1 6 2 4 

prueba de la corrección:

subsecuencias cada vez mayor en la columna 1 pueden ocurrir sólo en un solo grupo (el tamaño es < = ⌈√n⌉),

No 2 elementos de aumento de subsecuencias en la columna 2 están en el mismo grupo (no más de grupos ⌈√n⌉)