Wrap strings in an array to eliminate increasing subsequences

Question

The following problem is taken from the Problem with Algorithms (Problem 653):

You are given a matrix of numbers nx 2. Find an O (n log n) algorithm that permutes the rows in the array so that none of the columns in the array contains an increasing subsequence (which may not consist of adjacent elements of the array) longer than & lceil; & radic; n & Rceil;

I am not sure how to solve this. I think that he can use some kind of distinction between shoots and victories, but I can not find him.

Does anyone have any ideas how to solve this?

Answer 1

Here is my solution.

1) Sort rows by the first element from largest to lowest.

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

2) Divide it into groups from ⌈√n⌉ and what remains (no more than ⌈√n⌉ groups)

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

3) Sort the rows in each group according to the second element from largest to lowest

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

Proof of correctness:

The increase in subsequences in column 1 can occur in only one group (the size is <= ⌈√n⌉),

There are no two elements of increasing subsequences in column 2 in one group (no more than ⌈√n⌉ groups)