title: Algorithm for Human Towering
body: <p>In <a href="http://www.amazon.co.uk/Cracking-Coding-Interview-Fourth-Edition/dp/145157827X/ref=sr_1_2?ie=UTF8&amp;qid=1374531842&amp;sr=8-2&amp;keywords=cracking%20the%20coding%20interview" rel="noreferrer">Cracking the Coding Interview, Fourth Edition</a>, there is such a problem:</p>
  
  <blockquote>
    <p>A circus is designing a tower routine consisting of people standing
    atop one anoth- er’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.</p>
    
    <p>EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90)
    (75, 190) (60, 95) (68, 110) </p>
    
    <p>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)</p>
  </blockquote>
  
  <hr>
  
  <p>Here is its <strong>solution in the book</strong></p>
  
  <blockquote>
    <p>Step 1 Sort all items by height first, and then by weight This means that if all the heights are unique, then the items will be sorted by their height If heights are the same, items will be sorted by their weight</p>
    
    <p>Step 2 Find the longest sequence which contains increasing heights and increasing weights
    To do this, we:</p>
    
    <p>a) Start at the beginning of the sequence Currently, max_sequence is empty</p>
    
    <p>b) If, for the next item, the height and the weight is not greater than those of the previous item, we mark this item as “unfit”</p>
    
    <p>c) If the sequence found has more items than “max sequence”, it becomes “max sequence”</p>
    
    <p>d) After that the search is repeated from the “unfit item”, until we reach the end of the original sequence</p>
  </blockquote>
  
  <hr>
  
  <p>I have some questions about its solutions.</p>
  
  <p><strong>Q1</strong></p>
  
  <p>I believe this solution is wrong.</p>
  
  <p>For example</p>
  
  <p><code>(3,2) (5,9) (6,7) (7,8)</code></p>
  
  <p>Obviously, <code>(6,7)</code> is an unfit item, but how about <code>(7,8)</code>? According to the solution, it is NOT unfit as its h and w are bother bigger than <code>(6,7)</code>, however, it cannot be considered into the sequence, because <code>(7,8)</code> does not fit <code>(5,9)</code>.</p>
  
  <p>Am I right?</p>
  
  <p>If I am right, what is the fix?</p>
  
  <p><strong>Q2</strong></p>
  
  <p>I believe even if there is a fix for the above solution, the style of the solution will lead to at least <code>O(n^2)</code>, because it need to iterate again and again, according to step 2-d.</p>
  
  <p>So is it possible to have a O(nlogn) solution?</p>