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

thara

Jul 29, 2012@ 06:26:42can u plz tell me how this last par lcs works

Runhe Tian

Jul 29, 2012@ 15:27:20I 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.

vikram

Dec 24, 2012@ 12:34:57Hey 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

Prateek Govill

Jul 11, 2013@ 10:29:23could you pls send me the full code at my email id: prateekgovill@gmail.com.

Pls it’s urgent…..