Author |
Topic: Stacking problem (Read 4518 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Stacking problem
« on: Mar 24th, 2011, 6:50am » |
 Quote  Modify
|
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 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 to bottom: (56, 90)
(60,95) (65,100) (68,110) (70,150) (75,190)
This can be done in O(n^2) time very easily (by sorting the persons on height first and for the same height people on weight and then picking the longest increasing subsequence of weights).
Can we do this in O(n log n) ?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
spicy
Newbie
Gender: 
Posts: 8
|
|
Re: Stacking problem
« Reply #1 on: May 6th, 2011, 7:00am » |
Quote Modify
|
we can first sort the list by either of the dimension ,
then that dimension become constant and we run
longest increasing sub sequence solution on other dimension on sorted list.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
by this approach we do in o(nlogn).
have i missed something ?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print