algorithm - 増加するサブシーケンスを排除するために配列内の行を並べ替える

Question

次の問題は、アルゴリズムの問​​題（問題653）から抜粋したものです。

数のanx2行列が与えられます。配列のどちらの列にも⌈√n.⌉より長いサブシーケンス（連続する配列要素で構成されていない可能性がある）が含まれないように、配列内の行を並べ替えるO（n log n）アルゴリズムを見つけます。

これを解決する方法がわかりません。ある種の分割統治法の繰り返しを使うかもしれないと思いますが、見つけられないようです。

誰かがこれを解決する方法について何かアイデアがありますか？

Answer 1

これが私の解決策です。

1）最初の要素に従って行を最大から最小に並べ替えます。

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

2）それを⌈√n⌉のグループに分割し、残っているもの（⌈√n⌉グループ以下）

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

3）2番目の要素に従って、各グループの行を最大から最小の順に並べ替えます

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

正当性の証明：

列1のサブシーケンスの増加は、単一のグループでのみ発生する可能性があります（サイズは<=⌈√n⌉）、

列2の増加するサブシーケンスの2つの要素は、同じグループに含まれていません（⌈√n⌉グループ以下）