A circus is designing an act consisting of a tower 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 her. Given the heights and weights of each person in the circus, what is the largest possible number of people in such a tower?
Input(ht wt) : (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)
step 1: sort the people by their weights (in ascending order) --- O(nlogn)
step 2: sort the people by their height O(nlogn)
step 3: compute the longest common subsequence between weight and height O(n^2)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment