Algorithm for Human Towering

问题:

In Cracking the Coding Interview, Fourth Edition, there is such a problem:

A circus is designing a tower routine consisting of people standing atop one anoth- er’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)

---

Here is its solution in the book

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

Step 2 Find the longest sequence which contains increasing heights and increasing weights To do this, we:

a) Start at the beginning of the sequence Currently, max_sequence is empty

b) If, for the next item, the height and the weight is not greater than those of the previous item, we mark this item as “unfit”

c) If the sequence found has more items than “max sequence”, it becomes “max sequence”

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

---

I have some questions about its solutions.

Q1

I believe this solution is wrong.

For example

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

Obviously, (6,7) is an unfit item, but how about (7,8)? According to the solution, it is NOT unfit as its h and w are bother bigger than (6,7), however, it cannot be considered into the sequence, because (7,8) does not fit (5,9).

Am I right?

If I am right, what is the fix?

Q2

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

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

回答1:

You can solve the problem with dynamic programming.

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

We compute a sequence T_i, where T_i is a tower with person i at the top of maximal size. T_1 is simply {1}. We can deduce subsequent T_k from the earlier T_j — find the largest tower T_j that can take k's weight (w_j < w_k) and stand k on it.

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

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

回答2:

Tried solving this myself, did not meant to give 'ready made solution', but still giving , more to check my own understanding and if my code(Python) is ok and would work of all test cases. I tried for 3 cases and it seemed to work of 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)])   

回答3:

For example

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

Obviously, (6,7) is an unfit item, but how about (7,8)?

In answer to your Question - the algorithm first runs starting with 3,2 and gets the sequence (3,2) (5,9) marking (6,7) and (7,8) as unfit.

It then starts again on (6,7) (the first unfit) and gets (6,7) (7,8), and that makes the answer 2. Since there are no more "unfit" items, the sequence terminates with maximum length 2.

回答4:

After first sorting the array by height and weight, my code checks what the largest tower would be if we grabbed any of the remaining tuples in the array (and possible subsequent tuples). In order to avoid re-computing sub-problems, solution_a is used to store the optimal max length from the tail of the input_array.

The beginning_index is the index from which we can consider grabbing elements from (the index from which we can consider people who could go below on the human stack), and beginning_tuple refers to the element/person higher up on the stack.

This solution runs in O(nlogn) to do the sort. The space used is O(n) for the solution_a array and the copy of the 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)