Saturday, February 28, 2015

Largest number of people

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 book (Cracking the coding interview) provides a solution that requires extra O(2n) space. I don't think they are necessary. Basically, sort the list first by height then by weight (or vice versa, doesn't matter), this operation takes O(n log n). Then go through the list, track the current min (min), if min is less both in height and weight than the current element in the list, add the maxLength by 1, set min to current element. Because if either height or weight equals to min, this element is not considered, since the list is sorted, the element with the smallest height and weight is always prior to current element. This operation takes another O(n) time, so totally O(nlogn) time, with no extra space.


public class LongestSequence {
 private static class HeightNWeight {
  int h;
  int w;
  public HeightNWeight(int h, int w){
   this.h = h;
   this.w = w;
  }
  public String toString() {
   String s = "height: ";
   s += String.valueOf(h) + "; weight: " + String.valueOf(w);
   return s;
  }
 }
 public static int largestNumber(List people) {
  if (people == null || people.size() == 0)
   return 0;
  Collections.sort(people, new HNWComparator());
  HeightNWeight min = people.get(0);
  int maxLength = 1;
  for (int i = 1; i < people.size(); i++){
   if (min.h < people.get(i).h && min.w < people.get(i).w) {
    maxLength++;
    min = people.get(i);
   }
  }
  return maxLength;
 }
 private static class HNWComparator implements Comparator {
  public int compare(HeightNWeight hw1, HeightNWeight hw2) {
   if (hw1.h < hw2.h)
    return -1;
   else if (hw1.h > hw2.h)
    return 1;
   else if (hw1.w < hw2.w)
    return -1;
   else if (hw1.w < hw2.w)
    return 1;
   return 0;
  }
 }
 public static void main(String[] args) {
  List people = new ArrayList ();
  people.add(new HeightNWeight(56, 90));
  people.add(new HeightNWeight(60, 90));
  people.add(new HeightNWeight(60, 95));
  people.add(new HeightNWeight(65, 100));
  people.add(new HeightNWeight(68, 150));
  people.add(new HeightNWeight(70, 100));
  people.add(new HeightNWeight(70, 160));
  people.add(new HeightNWeight(75, 180));
  people.add(new HeightNWeight(80, 180));
  people.add(new HeightNWeight(85, 190));
  System.out.println(largestNumber(people));
 }

}

No comments:

Post a Comment