聚會等級 - 面試解決方案

Question

假設您是聚會顧問，並被聘請準備並舉辦公司聚會。公司中的每個員工都是B樹風格層次結構的一部分，並且享有派對評級值。爲了防止在直接主管在場的情況下對員工進行抑制，主管及其直接員工均不會被邀請。但是，任何一個組都可以被邀請。

設計一個算法來產生最大聚會排名總數的客人名單。

我的解決辦法是

• 監事將包含一個域的直接僱員的黨的隊伍的總和

執行自下而上的廣度優先搜索訪問最低主管樹中的子樹。對於每位主管，計算主管級別與直接員工總和之間的差異。如果員工隊伍總和大於主管級別，則所有受影響的員工將被添加到訪客列表中。

如果主管和員工排名之間的差異小於或等於零，則向上移動一個級別並執行上述比較，以查找下一級別子樹。

繼續向上一級，直到公司的負責人被分析，並打印出黨的總和和客人名單。

我對運行時間分析O(n log n -1)由於

log n-1 - 時間下降到最低的子樹

n - 比較的最大數量

我這個在接受記者採訪時提出了，但不禁感到我錯過了一些東西。我對分析和步驟是否正確？

Answer 1

我會計算，每個人在層次結構中自下而上的方式，兩個數字：

1. 如果那個人沒有參加，有多少他傳遞的下屬能參加。
2. 如果該人出席，他的下屬（包括他自己）中有多少人可以參加。

對於每個人，這是很容易計算給定每個直屬下屬的兩個數字（在O（B）時間其中，B是下屬的數量）。只要爲這個人嘗試兩種方式，併爲每個下屬使用適當的號碼。

因此，自下而上走，我認爲這是總共O（n）時間。