聚会等级 - 面试解决方案

Question

假设您是聚会顾问，并被聘请准备并举办公司聚会。公司中的每个员工都是B树风格层次结构的一部分，并且享有派对评级值。为了防止在直接主管在场的情况下对员工进行抑制，主管及其直接员工均不会被邀请。但是，任何一个组都可以被邀请。

设计一个算法来产生最大聚会排名总数的客人名单。

我的解决办法是

• 监事将包含一个域的直接雇员的党的队伍的总和

执行自下而上的广度优先搜索访问最低主管树中的子树。对于每位主管，计算主管级别与直接员工总和之间的差异。如果员工队伍总和大于主管级别，则所有受影响的员工将被添加到访客列表中。

如果主管和员工排名之间的差异小于或等于零，则向上移动一个级别并执行上述比较，以查找下一级别子树。

继续向上一级，直到公司的负责人被分析，并打印出党的总和和客人名单。

我对运行时间分析O(n log n -1)由于

log n-1 - 时间下降到最低的子树

n - 比较的最大数量

我这个在接受记者采访时提出了，但不禁感到我错过了一些东西。我对分析和步骤是否正确？

Answer 1

我会计算，每个人在层次结构中自下而上的方式，两个数字：

1. 如果那个人没有参加，有多少他传递的下属能参加。
2. 如果该人出席，他的下属（包括他自己）中有多少人可以参加。

对于每个人，这是很容易计算给定每个直属下属的两个数字（在O（B）时间其中，B是下属的数量）。只要为这个人尝试两种方式，并为每个下属使用适当的号码。

因此，自下而上走，我认为这是总共O（n）时间。