## Circus tower sorting 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)

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;
}

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 $D_{1}$. That is $O(n\log n)$.
Sort the data according to weight. Denote it as $D_{2}$. That is $O(n\log n)$.
Find the length of the Longest Common Sub-sequence of $D_{1}$ and $D_{2}$. Using dynamic programming, it’s $O(n^{2})$.

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>>();
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;
for (int j = 0; j < Y.size(); ++j)
array[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()];
}

Related
```

1. thara
Jul 29, 2012 @ 06:26:42

can u plz tell me how this last par lcs works

• Runhe Tian
Jul 29, 2012 @ 15:27:20

I have a Wiki link in the post. You can refer to that. But basically it’s a dynamic programming approach where you construct a table and populate the entry of the table step by step.

2. vikram
Dec 24, 2012 @ 12:34:57

Hey Can you explain why is the “array[i][j] + 1;” has plus +1 in the expression on line 46.. array[i + 1][j + 1] = array[i][j] + 1;

Thanks

3. Prateek Govill
Jul 11, 2013 @ 10:29:23

could you pls send me the full code at my email id: prateekgovill@gmail.com.
Pls it’s urgent…..