Skip to content

17.08. Circus Tower

Description

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: height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]

Output: 6

Explanation: The longest tower is length 6 and includes from top to bottom: (56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

Note:

  • height.length == weight.length <= 10000

Solutions

Solution 1: Sorting + Discretization + Binary Indexed Tree

First, we sort all people in ascending order by height. If the heights are the same, we sort them in descending order by weight. This way, we can transform the problem into finding the longest increasing subsequence of the weight array.

The longest increasing subsequence problem can be solved using dynamic programming with a time complexity of $O(n^2)$. However, we can optimize the solution process using a Binary Indexed Tree, which reduces the time complexity to $O(n \log n)$.

The space complexity is $O(n)$, where $n$ is the number of people.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] = max(self.c[x], delta)
            x += x & -x

    def query(self, x):
        s = 0
        while x:
            s = max(s, self.c[x])
            x -= x & -x
        return s


class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        arr = list(zip(height, weight))
        arr.sort(key=lambda x: (x[0], -x[1]))