ВИнтервью о взломе кодов, четвертое изданиеесть такая проблема:

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

ПРИМЕР: Ввод (мас., Мас.): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

Результат: самая длинная башня имеет длину 6 и включает в себя сверху вниз: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

Вот еерешение в книге

Шаг 1 Сортировка всех элементов сначала по росту, а затем по весу. Это означает, что если все высоты уникальны, то элементы будут отсортированы по их высоте. Если высоты одинаковы, элементы будут отсортированы по их весу.

Шаг 2 Найдите самую длинную последовательность, которая содержит увеличение высоты и увеличение веса. Для этого мы:

а) Начало в начале последовательности В настоящее время max_sequence пуст

б) Если для следующего предмета рост и вес не больше, чем у предыдущего предмета, мы помечаем этот предмет как «непригодный»

c) Если найденная последовательность имеет больше элементов, чем «максимальная последовательность», она становится «максимальной последовательностью»

г) После этого поиск повторяется с «непригодного предмета», пока мы не достигнем конца первоначальной последовательности

У меня есть несколько вопросов о его решениях.

Q1

Я считаю, что это решение неверно.

Например

(3,2) (5,9) (6,7) (7,8)

Очевидно, что(6,7) это непригодный предмет, но как насчет(7,8)? Согласно решению, оно НЕ подходит, так как его h и w больше, чем(6,7)Однако это не может рассматриваться в последовательности, потому что(7,8) не подходит(5,9).

Я прав?

Если я прав, что за исправление?

Q2

Я считаю, что даже если есть исправление для вышеуказанного решения, стиль решения приведет по крайней мереO(n^2)потому что это нужно повторять снова и снова, в соответствии с шагом 2-й.

Так возможно ли иметь решение O (nlogn)?