Задача о стопках книг

[worm2]

Имеются книги, каждая из которых характеризуется шириной и высотой (толщина нас не интересует; поворачивать книги так, чтобы ширина и высота поменялись местами, нельзя). Книги нужно разложить по стопкам. Стопка называется правильной, если книга, лежащая выше, не шире и не выше книги, лежащей под ней.
Хочется разложить книги на наименьшее возможное число правильных стопок.
Хочется также, чтобы процесс разложения по стопкам был по возможности быстрым. Медленнее, чем такой же процесс сортировки только по ширинам или только по высотам, не более чем в фиксированное число раз. Если это возможно, конечно.

[Sender]

Так это же задача о разбиении частично упорядоченного множества на минимальное число цепей. Алгоритм можно посмотреть, к примеру, здесь. Кажется, быстрее, чем за $O(n^\frac{5}{2})$ сделать не получится.

[worm2]

Жалко. Не знал, что это классическая задача. Был почти уверен, что здесь $O(n^2)$ пройдёт и даже думал об $O(n\log n)$.
P.S. По ссылке у меня картинки не открываются.

-- Пн апр 02, 2012 12:53:34 --

Что-то у меня ступор. Не могу понять, что не так в "жадном" алгоритме:

1) Берём 1-ю книгу и сравниваем с остальными. В результате у нас получается правильная стопка (=цепь), в которую входит 1-я книга. Откладываем правильную стопку в сторону.
2) С оставшимися книгами осуществляем ту же операцию, пока не исчерпаются все книги.

По построению книги, которые стоят в начале каждой цепи (внизу каждой стопки), образуют антицепь. Значит, по теореме Дилворта (хотя и без теоремы понятно, что две книжки из антицепи никогда в одной цепи не окажутся) уменьшить число цепей нельзя.
Получается по осторожным подсчётам $O(n^2 \log n)$. По неосторожным — $O(n^2)$

[Sender]

worm2 в сообщении #554753 писал(а):

Что-то у меня ступор. Не могу понять, что не так в "жадном" алгоритме

Не забывайте, что каждый элемент цепи должен быть сравним со всеми остальными, а не только с первым, т.е. книги, стоящие в началах ваших цепей, вполне могут быть сравнимы друг с другом.

Алгоритм можно найти здесь в разделе "Offline Algorithms".

[worm2]

Да, Вы правы. Я кругом ошибся.

Я писал(а):

1) Берём 1-ю книгу и сравниваем с остальными. В результате у нас получается правильная стопка (=цепь), в которую входит 1-я книга.

1-я ошибка: никакая это не цепь, а просто набор книг, сравнимых с первой. То, что они друг с другом сравнимы, ниоткуда не следует.

Я писал(а):

По построению книги, которые стоят в начале каждой цепи (внизу каждой стопки), образуют антицепь.

2-я ошибка. Спутал начало цепи и первую выбранную книгу, с которой шло сравнение в п. 1. Даже если бы здесь были цепи, с чего бы это их начала были несравнимы?

Сильно недооценил задачу...