排列数组中的行以消除增加的子序列

Question

以下问题摘自算法问题（问题 653）：

给你一个 x 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

正确性证明：< /strong>

第 1 列中的递增子序列只能发生在单个组中（大小 <= ⌈√n⌉），

第 2 列中的递增子序列中没有 2 个元素在同一组（不超过⌈√n⌉组）