Перестановка строк в массиве для устранения возрастающих подпоследовательностей

Question

Следующая задача взята из Задачи по алгоритмам (задача 653):

Вам дана матрица чисел n x 2. Найдите алгоритм O (n log n), который переставляет строки в массиве так, чтобы ни один столбец массива не содержал возрастающую подпоследовательность (которая может не состоять из смежных элементов массива) длиннее, чем & lceil; & radic; n. & Rceil;

Я не уверен, как это решить. Я думаю, что он может использовать какое-то повторение «разделяй и властвуй», но я не могу его найти.

У кого-нибудь есть идеи, как решить эту проблему?

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⌉), </p>

Нет элементов 2 возрастающих подпоследовательностей в столбце 2, кромев одной группе (не более ⌈√n⌉ групп)