algorithm - 政党排名-面试解决方案

Question

假设您是派对顾问，受雇准备和举办公司派对。公司中的每个员工都是 B 树样式层次结构的一部分，并被赋予党等级值。为防止员工在直接主管在场的情况下受到抑制，主管及其直接员工均不会被邀请。但是，可以邀请任何一组。

设计一个算法来生成最大派对排名总和的客人名单。

我的解决方案是

• 主管将包含一个字段，用于显示直接雇员的党员等级总和

执行自下而上的广度优先搜索以访问树中最低的主 pipe 树。对于每个主管，计算主管党员等级与直接雇员总和之间的差异。如果员工党等级之和大于主管等级，则所有受影响的员工将被添加到客人名单中。

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

层层递进，分析出公司负责人，打印出党员总和及嘉宾名单。

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

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

n - 最大比较次数

我在一次采访中想到了这个，但忍不住觉得我错过了什么。我的分析和步骤是否正确？

Answer 1

我会以自下而上的方式为层次结构中的每个人计算两个数字:

1. 如果那个人没有参加，他的下属中有多少人可以参加。
2. 如果那个人确实参加了，他的下属中有多少人(包括他自己)可以参加。

对于每个人来说，这很容易计算给每个直属下属的两个数字(在 O(B) 时间内，其中 B 是下属的数量)。只需为这个人尝试两种方法，并为每个下属使用适当的数字。

所以对于自下而上的行走，我认为总共需要 O(n) 时间。