Cracking The Coding Interview(5th ed): Chp 11, Ques 7
Question: 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 height and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
My doubt:
- In the solution given in the book it is clearly mentioned in the text that sorting the elements will make the solution too trivial then why elements have been sorted initially in the code?
If the elements do not need to stay in the same(relative) order, then we would simply sort the array. This makes the problem too trivial, so let's assume that the elements need to stay in the same relative order.
Here is the code from the book where sorting has been done(First three lines of the code):
ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> items) { Collections.sort(items); return longestIncreaingSequence(items); } 1 Answers
Answers 1
The proposed solution is composed of 2 steps:
- sort by weight
- find the longest increasing subsequence on the heights
The quoted sentence is not relative to the first step, but to the second step (finding the longest increasing subsequence) and it is explaining that we can't just sort the heights because we can't change their order since they are already sorted by their weights.
Take a look at this example with 5 people:
weights: 4 5 1 7 2 heights: 6 3 5 4 1 Result after step 1 (sorting by weight):
weights: 1 2 4 5 7 heights: 5 1 6 3 4 Now, looking at the heights we can see that the longest increasing subsequence is 1 3 4 which tell us that the solution is composed of 3 people. To obtain that result we can't just sort by heights because since they are already sorted by their weight...
... the elements need to stay in the same relative order.
So we need to use a longest increasing subsequence algorithm instead.
0 comments:
Post a Comment