Find the largest possible number of people in such a tower

First, let's see the 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 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)

But I don't quite understand the solution as follows:

Proposed solution by the book:

• Step 1. Sort all items by height first, and then by weight. This means that if all the heights a开发者_JAVA技巧re unique, then the items will be sorted by their height. If heights are the same, items will be sorted by their weight. Example: »»Before sorting: (60, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68,110). »After sorting: (56, 90), (60, 95), (60,100), (68, 110), (70,150), (75,190).

• Step 2. Find the longest sequence which contains increasing heights and increasing weights. To do this, we:

• a) Start at the beginning of the

  sequence. Currently, max_sequence is empty.

• 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”

  c) If the sequence found has more items than “max sequence”, it becomes “max sequence”.

• d) After that the search is repeated from the “unfit item”,

  until we reach the end of the

  original sequence.

  public class Question {
  ArrayList<HtWt> items;
  ArrayList<HtWt> lastFoundSeq;
  ArrayList<HtWt> maxSeq;
  
  
  / Returns longer sequence
  ArrayList<HtWt> seqWithMaxLength(ArrayList<HtWt> seq1, ArrayList<HtWt> seq2) {
      return seq1.size() > seq2.size() ? seq1 : seq2;
  }
  
  
  // Fills next seq w decreased wts&returns index of 1st unfit item.
  int fillNextSeq(int startFrom, ArrayList<HtWt> seq) {
    int firstUnfitItem = startFrom;
    if (startFrom < items.size()) {
        for (int i = 0; i < items.size(); i++) {
          HtWt item = items.get(i);
          if (i == 0 || items.get(i-1).isBefore(item)) {
              seq.add(item);
          } else {
              firstUnfitItem = i;
          }
        }
    }
    return firstUnfitItem;
  }
  
  
  // Find the maximum length sequence
  void findMaxSeq() {
    Collections.sort(items);
    int currentUnfit = 0;
    while (currentUnfit < items.size()) {
        ArrayList<HtWt> nextSeq = new ArrayList<HtWt>();
        int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
        maxSeq = seqWithMaxLength(maxSeq, nextSeq);
        if (nextUnfit == currentUnfit) 
          break;
        else 
          currentUnfit = nextUnfit;
    }
  }
  

  }

  Question,

  1> what is the usage of the function fillNextSeq? 2> why check "items.get(i-1).isBefore(item)" rather than compare the current item with the latest one in the seq?

Assume the sorting list is (1, 5), (2, 1), (2, 2), based on the function of fillNextSeq,

first (1, 5) will be pushed into the sequence. Then item (2, 1) will not be pushed into the sequence b/c weight of (2,1) is smaller than (1, 5). Next, since (2, 1) is before (2, 2), so (2, 2) will be pushed into the sequence.

Now, the sequence contains (1, 5) and (2, 2) which is not correct b/c the weight of (1, 5) is larger than that of (2, 2).

Thank you

The usage of fillNextSeq is to fetch the next sequence of increasing height/weight in your group. It does this by adding successive items to the ArrayList seq until it comes across a heavier or taller person.

The function of items.get(i-1).isBefore(item) is to check if the next person is shorter and lighter than the current one. Remember that you have already sorted your people by height and weight, so if the next person in sequence is taller or heavier than the current person then they will come before the current person in the sorted array. So the line in question IS comparing the current item with the latest one in the sequence, it's just doing it by comparing their positions in the sorted array.

Hope this helps, good luck!

I think we can use dynamic programming resolve this problem. Here is my idea:

L(j) -- the largest possible people ending at j ( 0 < j < n)
L(j) = max { L(i) } + 1 where i<j && ht(i)< ht(j) && wt(i)< wt(j)
we're looking for max{L(j)} where 0<j<n.

For each j, we hold an array list. The ht and wt of the persons within the array list increases. When dealing with the jth person, we do binary search on the array list of all the

List<HtWt> F( HtWt[] in, int n){

   ArrayList<HtWt> out = new ArrayList<HtWt>(n);
   out[0].add(int[0]); 

   int maxl = 0, tj = 0;

   for(int j = 1; j < n; j++){

      // choose the longest among all available
      int jl = 0, ti = 0, tp = 0;

      for( i = 0; i < j; i++){

         // find the first greater element in out[i]
         int x = F(out[i], in[j]);

         // find an appropriate position in i to insert j
         if ( x != -1)  
         {
            // compare with the longest list found so far
            if( (out[i].size + 1) > jl ){
              jl = (out[i].size + 1);
              ti = i;
              tp = x;
          }// if             
      }// for i
     out[j] = out[i];
     out[j].add( tp, o[j]);

     if ( out[j].size > maxl){
       maxl = out[j].size
       tj = j;
     } // if
   } // for j

   return out[tj];
 }  // F

 running time: n + nlogn

 For example, (80, 10), (80, 80), (90, 10), (90, 20), (90, 30)
 j = 0, len = 1, out[0] = (80,10) 
 j = 1, len = 1, out[1] = (80,80)
 j = 2, len = 1 , out[2] = (90, 10)
 j = 3, len = 2, out[3] = (80,10)->(90,20)
 j = 4, len = 1, out[4] = (90, 30)

I have written a solution in c# which has two parts.

Part 1:- create a comparer which sorts on basis of both height and weight (height && weight) in ascending order.

Part 2 :- linear search on the sorted array from the end such that a[i]should be less that a[i-1] in both height and weight.

below is the code. i have some some unit test cases and have checked the code is working fine. but some how i feel there is a bug hidden in this solution. Request the Experts here to validate the code.

My Person class which implements IComparer

public class Person : IComparer<Person>
{

    public double Height { get; set; }
    public double Weight { get; set; }

    public int Compare(Person p1, Person p2)
    {

        if ((p1.Height > p2.Height) && (p1.Weight > p2.Weight))
            return 1;

        return -1;
    }

}

My main method

public int NumberOfPeople(Person[] p)
    {

        if (p == null || p.Length == 0)
            return -1;

        Array.Sort(p, new Person());
        int last = p.Length - 1;
        int count = 1;
        for (int i = p.Length - 2; i >= 0 ; i--)
        {
            if ((p[i].Height < p[last].Height) && p[i].Weight < p[last].Weight)
            {
                last = i;
                count++;
            }
        }
        return count;
    }

any sort of help would be appreciated.