I'm working through Cracking the Coding Interview 6th ed, and I'm having trouble with the Circus Tower problem (number 17.8). I have a solution that I think runs in O(N logN) time, but the book's solution (which is different) says that the O(N logN) solution is very complex, but my code is not. I'd like some help figuring out if my solution is correct, and if it actually runs in O(N logN) time. I want to understand why I am wrong (or right), so any details would be helpful.
A circus is designing a tower routine consisting of people standing atop one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
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)
Here are some sample inputs and what my code returns:
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
Your solution is wrong. If you run
circus_tower([[1,1],[1,7],[1,9],[2,2],[2,6],[3,3],[3,5],[4,4]])
it returns 2 while the longest subsequence ([1,1]<[2,2]<[3,3]<[4,4]) has length 4.
The problem with your code is that you only find contiguous subsequences.