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

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:

  1. Sort the data according to height. Denote it as D_{1}. That is O(n\log n).
  2. Sort the data according to weight. Denote it as D_{2}. That is O(n\log n).
  3. 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>>();
		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()];
	}
Advertisements

4 Comments (+add yours?)

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

    can u plz tell me how this last par lcs works

    Reply

    • 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.

      Reply

  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

    Reply

  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…..

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: