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)

**My initial thoughts:**

Sort the data according to height. If same height, sort according to weight then. After sorting, scan the data to find the maximum ordering sequence. Starting from the 1st element, if the next element is ordered, keep going. Otherwise, mark the 1st invalid element. Next time, start from the invalid element. In each scan, store the length of the sequence. Output the largest one.

**My initial codes:**

public static int highestTower(List<Pair<Integer>> data) {
class HeightComparator implements Comparator<Pair<Integer>> {
@Override
public int compare(Pair<Integer> p1, Pair<Integer> p2) {
if (!p1.getX().equals(p2.getX()))
return p1.getX() - p2.getX();
else {
return p1.getY() - p2.getY();
}
}
}
Collections.sort(data, new HeightComparator());
int count = 1;
int max_count = -Integer.MAX_VALUE;
int fromIndex = 0;
boolean notchanged = true;
while (fromIndex != data.size()) {
Pair<Integer> base = data.get(fromIndex);
for (int i = fromIndex; i < data.size() - 1; ++i) {
Pair<Integer> item = data.get(i);
if (item.getX() > base.getX() && item.getY() > base.getY()) {
count++;
base = item;
} else if (notchanged) {
fromIndex = i;
notchanged = false;
}
if (count > max_count)
max_count = count;
}
}
return max_count;
}

**Comments after running:**

It doesn’t work. Infinite loop. After debugging, the program runs correctly but the logic behind is actually wrong hence the output is not correct. What I try to do is as follows:

Suppose, after sorting we have: (1, 3), (2, 2), (3, 1), (4, 6), (5, 4), (6, 5)

Then after 1st scan, we have the max sequence as (1, 3), (4, 6) and the invalid index is 1 (i.e., from (2, 2)). However, I’m expecting we have (1, 3), (5, 4) and (6, 5) as the max sequence.

**Solution:**

It goes as follows:

- Sort the data according to height. Denote it as . That is .
- Sort the data according to weight. Denote it as . That is .
- Find the length of the Longest Common Sub-sequence of and . Using dynamic programming, it’s .

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()];
}