Circus tower sorting problem

Problem

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)

Solution

Proposed solution by the book:

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: A(60, 100),  B(70, 150), C(56, 90) D(75, 190) E(60, 95) F(68,110). »After sorting:
   

   C (56, 90),
   E (60, 95),
   A (60,100),
   F (68, 110),
   B (70,150),
   D (75,190).
   

2. Find the longest sequence which contains increasing heights and increasing weights. To do this, we:
   • Start at the beginning of the sequence. Currently, max_sequence is empty.
   • 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"
     

     (60,95)         (65,100)         (75,80)         (80, 100)
                                    (unfit item)
     

   • If the sequence found has more items than “max sequence”, it becomes “max sequence”.
   • After that the search is repeated from the “unfit item”,
     until we reach the end of the original sequence.

Time Complexity

• Sort the data according to height. Denote it as D1. That is O(nlog n). 
• Sort the data according to weight. Denote it as D2. That is O(nlog n). 
• Find the length of the Longest Common Sub-sequence of D1 and D2. Using dynamic programming, it's O(n^2).

Here is the code in java

public static int highestTower(List<Pair<Integer>> data) {
 
    class HeightComparator implements Comparator<Pair<Integer>> {
        private int which;
 
        public HeightComparator(int which) {
            this.which = which;
        }
 
        @Override
        public int compare(Pair<Integer> p1, Pair<Integer> p2) {
            if (which == 0) {
                if (!p1.getX().equals(p2.getX()))
                    return p1.getX() - p2.getX();
                else {
                    return p1.getY() - p2.getY();
                }
            } else {
                if (!p1.getY().equals(p2.getY()))
                    return p1.getY() - p2.getY();
                else {
                    return p1.getX() - p2.getX();
                }
            }
        }
    }
 
    List<Pair<Integer>> copy = new ArrayList<Pair<Integer>>();
    copy.addAll(data);
    Collections.sort(data, new HeightComparator(0));
    Collections.sort(copy, new HeightComparator(1));
    return LCSLength(data, copy);
}
 
private static int LCSLength(List<Pair<Integer>> X, 
        List<Pair<Integer>> Y) {
    int[][] array = new int[X.size() + 1][Y.size() + 1];
    for (int i = 0; i < X.size(); ++i)
        array[i][0] = 0;
    for (int j = 0; j < Y.size(); ++j)
        array[0][j] = 0;
    for (int i = 0; i < X.size(); ++i) {
        for (int j = 0; j < Y.size(); ++j) {
            if (X.get(i).equals(Y.get(j)))
                array[i + 1][j + 1] = array[i][j] + 1;
            else
                array[i + 1][j + 1] = 
                    Math.max(array[i + 1][j], array[i][j + 1]);
        }
    }
    return array[X.size()][Y.size()];
}

References
http://tianrunhe.wordpress.com/2012/04/01/circus-tower-sorting-problem/
http://stackoverflow.com/questions/6893041/dynamic-programming-question
http://martinm2w.wordpress.com/2012/06/06/9-7-sort-search-circus-tower-largest-possible-number-of-ppl/