人类高耸的算法

Question

在Cracking the Coding Interview, Fourth Edition ，有这样一个问题:

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)

---

这是它的书中的解决方案

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

---

我对它的解决方案有一些疑问。

第一季度

我认为这个解决方案是错误的。

例如

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

显然，(6,7) 是不合适的项，但是 (7,8) 呢？根据解决方案，它不是不适合，因为它的 h 和 w 比 (6,7) 大，但是，它不能被考虑到序列中，因为 (7,8) 不适合 (5,9)。

我说得对吗？

如果我是对的，解决方法是什么？

第二季度

我相信即使有针对上述解决方案的修复，解决方案的样式将导致至少O(n^2)，因为它需要一次又一次地迭代，根据到第 2-d 步。

那么有没有可能有一个O(nlogn)的解呢？

Answer 1

你可以用动态规划来解决这个问题。

按高度对剧团进行排序。为简单起见，假设所有高度 h_i 和重量 w_j 都是不同的。因此h_i是递增序列。

我们计算一个序列 T_i，其中 T_i 是一座塔，第 i 个人位于最大尺寸的顶部。 T_1 就是{1}。我们可以从前面的 T_j 推导出后续的 T_k——找到最大的塔 T_j，它可以承受 k 的重量(w_j < w_k)并站在上面。

剧团中可能最大的塔就是 T_i 中最大的塔。

此算法需要 O(n**2) 时间，其中 n 是剧团的基数。