P*******b
发帖数: 1001 | 1 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 sho
rter and lighter than the person below him or her. Given the heights and wei
ghts of each person in the circus, write a method to compute the largest pos
sible number of peoplein such a tower.
EXAMPLE:
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 | l******c
发帖数: 2555 | 2 longest increasing subsequence | I**A
发帖数: 2345 | 3 from career-cup
Let’s assume the following input: (65, 100) (70, 150) (56, 90) (64,140) (75
, 190) (60, 95) (68,
110).
Since we know that each person must be shorter and lighter than the person
below him/her,
we will sort our input based on either weight or height.
Let’s assume that we have sorted our input based on height:
(56, 90) (60, 95) (64, 140) (65, 100) (68, 110) (70, 150) (75, 190)
Now we know that our output should be a subsequence (may not be contiguous
but should
have same relative o |
|
