Human Lifting Algorithm

Question

Cracking the Coding Interview, fourth edition , has this problem:

The circus designs a tower routine consisting of people standing on one shoulder. For practical and aesthetic reasons, each person should 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 way to calculate the maximum possible number of people in such a tower.

Example: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110).

Exit: the longest tower is length 6 and includes top to bottom: (56, 90) (60.95) (65 100) (68 110) (70,150) (75,190)

---

Here is his solution in the book

Step 1 First sort all the elements by height, and then by weight. This means that if all heights are unique, then the items will be sorted by their height. If the heights are the same, items will be sorted by their weight.

Step 2 Find the longest sequence that contains an increase in height and an increase in weight. To do this, we:

a) Start at start of sequence Currently max_sequence is empty

b) If for the next element the height and weight are not greater than the previous element, we mark this element as “unusable”

c) If the sequence found contains more elements than the "maximum sequence", it becomes the "maximum sequence"

d) After that, the search is repeated from the “unsuitable element” until we reach the end of the original sequence

---

I have some questions about his solutions.

Q1

I believe this decision is wrong.

for instance

(3,2) (5,9) (6,7) (7,8)

Obviously, (6,7) is unsuitable, but what about (7,8) ? According to the decision, it is NOT unsuitable, since its h and w are greater than (6,7) , but it cannot be considered in sequence, because (7,8) does not fit (5,9) .

I'm right?

If I am right, what is the fix?

Q2

I believe that even if there is a correction for the above solution, the style of the solution will lead to at least O(n^2) , because it needs to be repeated again and again, according to step 2-d.

So, is it possible to have an O (nlogn) solution?

Answer 1

You can solve the problem with dynamic programming.

Sort the troupe by height. For simplicity, suppose that all heights h_i and weights w_j are different. Thus, h_i is an increasing sequence.

We compute the sequence T_i, where T_i is the tower with face I at the top of the maximum size. T_1 is just {1}. We can derive the next T_k from the earlier T_j - find the largest tower T_j, which can take k weight (w_j <w_k) and put k on it.

The largest tower of the troupe then is the largest of T_i.

This algorithm takes time O (n ** 2), where n is the power of the troupe.

Answer 2

I tried to solve it myself, didn’t want to give a “ready-made solution”, but still gave more to check my own understanding and if my code (Python) is in order and will work in all test cases. I tried in 3 cases, and this seems to be the correct answer.

 #!/usr/bin/python #This function takes a list of tuples. Tuple(n):(height,weight) of nth person def htower_len(ht_wt): ht_sorted = sorted(ht_wt,reverse=True) wt_sorted = sorted(ht_wt,key=lambda ht_wt:ht_wt[1]) max_len = 1 len1 = len(ht_sorted) i=0 j=0 while i < (len1-1): if(ht_sorted[i+1][1] < ht_sorted[0][1]): max_len = max_len+1 i=i+1 print "maximum tower length :" ,max_len ###Called above function with below sample app code. testcase =1 print "Result of Test case ",testcase htower_len([(5,75),(6.7,83),(4,78),(5.2,90)]) testcase = testcase + 1 print "Result of Test case ",testcase htower_len([(65, 100),(70, 150),(56, 90),(75, 190),(60, 95),(68, 110)]) testcase = testcase + 1 print "Result of Test case ",testcase htower_len([(3,2),(5,9),(6,7),(7,8)]) 

Answer 3

for instance

(3.2) (5.9) (6.7) (7.8)

Obviously, (6.7) is unsuitable, but what about (7.8)?

In response to your question - the algorithm starts with 3.2 and gets the sequence (3.2) (5.9), designating (6.7) and (7.8) as unsuitable.

Then it starts again at (6.7) (the first unsuitable) and gets (6.7) (7.8), and this makes answer 2. Since there are no more “unsuitable” elements, the sequence ends with a maximum length of 2.

Answer 4

After the first sorting of the array by height and weight, my code checks what the largest tower will be if we take any of the remaining tuples in the array (and possible subsequent tuples). To avoid recalculations, solution_a used to store the optimal maximum length from the tail of input_array .

beginning_index is the index from which we can consider the capture of elements from (the index from which we can consider people who can go lower in the human stack), and beginning_tuple refers to the element / person above the stack.

This solution works in O (nlogn) to sort. The used O (n) space for the solution_a array and a copy of input_array .

 def determine_largest_tower(beginning_index, a, beginning_tuple, solution_a): # base case if beginning_index >= len(a): return 0 if solution_a[beginning_index] != -1: # already computed return solution_a[beginning_index] # recursive case max_len = 0 for i in range(beginning_index, len(a)): # if we can grab that value, check what the max would be if a[i][0] >= beginning_tuple[0] and a[i][1] >= beginning_tuple[1]: max_len = max(1 + determine_largest_tower(i+1, a, a[i], solution_a), max_len) solution_a[beginning_index] = max_len return max_len def algorithm_for_human_towering(input_array): a = sorted(input_array) return determine_largest_tower(0, a, (-1,-1), [-1] * len(a)) a = [(3,2),(5,9),(6,7),(7,8)] print algorithm_for_human_towering(a)