Вопрос:
Я работаю через 6-е издание «Взлома кодирования», и у меня проблемы с Цирковой башней (номер 17.8).У меня есть решение, которое, как мне кажется, выполняется за время O (N logN), но в книге (которая отличается) говорится, что решение O (N logN) очень сложное, а мой код - нет.Мне нужна помощь, чтобы выяснить, правильно ли моё решение и действительно ли оно выполняется за O (N logN).Я хочу понять, почему я не прав (или прав), поэтому любые подробности были бы полезны.
Вот текст проблемы:
Цирк проектирует вышку, состоящую из людейстоя на плечах друг друга.По практическим и эстетическим соображениям каждый человек должен быть короче и легче человека ниже его или ее.Учитывая рост и вес каждого человека в цирке, напишите метод вычисления максимально возможного числа людей в такой башне.
Мое решение:
def circus_tower(people):
# People is a list of tuples of length 2, where item[0] is their height, and item[1] is their weight.
if len(people) == 0:
return 0
people = sorted(people, key=lambda x: x[0]) # Sort people by heights. O(P*logP).
start = 0
end = 0
longest_sequence = 0
for i in range(1, len(people)): # O(P).
if people[i][1] > people[i-1][1]: # Weight check.
end = i
else:
longest_sequence = end - start + 1
start = i
end = i
return max(longest_sequence, end - start + 1)
Здесьпримеры ввода и что возвращает мой код:
circus_tower([(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110)])
6
circus_tower([(65, 100), (70, 150), (56, 90), (75, 190), (65, 95), (68, 110)])
4
circus_tower([(56, 90), (65, 95), (72, 100), (68, 90), (70, 150), (75, 190)])
2
circus_tower([])
0