Find the largest possible number of people in such a tower

Question

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 are 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

Answer 1

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!