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)
import java.util.ArrayList; import java.util.Collections; import java.util.*; public class heightWeightQueue { public class HTWT implements Comparable { public int HT; public int WT; public HTWT(int h, int w){ HT = h; WT = w; } public int compareTo(Object S){//second object HTWT second = (HTWT) S;//cast to HTWT if(this.HT != second.HT){ return((Integer) this.HT).compareTo((Integer) second.HT); } else{ return((Integer) this.WT).compareTo((Integer) second.WT); } } public String toString(){ return "(" + HT + ", " + WT + ")"; } public boolean isBefore(HTWT second){ if(this.HT < second.HT && this.WT < second.WT){ return true; } else{ return false; } } } ArrayList<HTWT> items; ArrayList<HTWT> last; ArrayList<HTWT> maxSeq; //return longer sequence ArrayList<HTWT> MaxLength(ArrayList<HTWT> first, ArrayList<HTWT> second){ return first.size() > second.size() ? first: second;//return arraylist not size !!! } public int fillNextSeq(int start, ArrayList<HTWT> seq){ int first = start; if(start < items.size()){ for(int i = 0 ; i <items.size();i++ ){ HTWT item = items.get(i); if(i==0||items.get(i-1).isBefore(item)){ seq.add(item); } else{ first = i; } } } return first; } public void findMaxSeq(){ Collections.sort(items);//arralist has to be sorted by collection int current = 0; while(current < items.size()){ ArrayList<HTWT> next = new ArrayList<HTWT>(); int nextUnfit = fillNextSeq(current, next); maxSeq = MaxLength(maxSeq,next); if(nextUnfit == current){break;} else{ current = nextUnfit; } } } public void initilize(){ items = new ArrayList<HTWT>(); last = new ArrayList<HTWT>(); maxSeq = new ArrayList<HTWT>(); HTWT item = new HTWT(65,60); items.add(item); item = new HTWT(70, 150); items.add(item); item = new HTWT(70, 150); items.add(item); item = new HTWT(70, 150); items.add(item); item = new HTWT(70, 150); items.add(item); item = new HTWT(70, 150); items.add(item); } public void printList(ArrayList<HTWT> list) { for (HTWT item : list) { System.out.println(item.toString() + " "); } } public void printResult() { printList(maxSeq); } public static void main(String[] args){ heightWeightQueue offer = new heightWeightQueue(); offer.initilize(); offer.findMaxSeq(); offer.printResult(); } }