longest height of tower

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)

The problem looks like sorting, we can sort the person by height, if the height are the same, we sort by weight. Then we go through the sorted to find the longest continuous sequence.

	public static int longestSeq(Person[] p) {
		Arrays.sort(p, new Comparator<Person>() {
			@Override
			public int compare(Person p1, Person p2) {
				if (p1.height > p2.height)
					return 1;
				else if (p1.height < p2.height)
					return -1;
				else {
					if (p1.weight > p2.weight)
						return 1;
					else if (p2.weight < p2.weight)
						return -1;
				}
				return 0;
			}
		});
		int maxLen = 1;
		int len = 1;
		Person pre = p[0];
		for (int i = 1; i < p.length; i++) {
			Person cur = p[i];
			if (onTop(pre, cur)) {
				len++;
			}
			else {
				len = 1;
			}
			maxLen = Math.max(maxLen, len);
		}
		return maxLen;
	}
	
	private static boolean onTop(Person p1, Person p2) {//return true if person1 can be on top of person2
		return (p1.height <= p2.height && p1.weight <= p2.weight);
	}  

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