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

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

ПРИМЕР: Ввод (мас., Мас.): (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)?