在陣列中的行置換來消除增加子序列

Question

以下問題是從Problems on Algorithms採取（問題653）：

您正在給定數字的正×2矩陣。找到一個O（n log n）算法，用於對數組中的行進行置換，使得數組的兩列均不包含比⌈ √ 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）分類排第二元件從最大到正確性的最低

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

證明：

個在列1中增加子序列可以只發生在單組（大小是< =⌈√n⌉）

在第2欄增加子序列的2個元素是在同一個組（不超過⌈√n⌉組的詳細）