wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Stacking problem
        
(Message started by: birbal on Mar 24^th, 2011, 6:50am)

Title: Stacking problem
Post by birbal on Mar 24^th, 2011, 6:50am

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) ?

Title: Re: Stacking problem
Post by spicy on May 6^th, 2011, 7:00am

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 ?