あなたはパーティー コンサルタントで、会社のパーティーを準備して主催するために雇われているとします。会社のすべての従業員は B ツリー スタイルの階層の一部であり、パーティ ランク値が与えられます。直属の上司の面前での従業員の妨害を防ぐため、上司とその直属の従業員は招待されません。ただし、どちらのグループも招待できます。
最大のパーティー ランク合計のゲスト リストを生成するアルゴリズムを設計します。
私の解決策は
- スーパーバイザーには、直属の従業員のパーティ ランクの合計のフィールドが含まれます。
ボトムアップの幅優先検索を実行して、ツリー内の最下位のスーパーバイザー サブツリーにアクセスします。上司ごとに、上司のパーティ ランクと直属の従業員の合計との差を計算します。従業員パーティ ランクの合計が上司のランクよりも大きい場合、影響を受けるすべての従業員がゲスト リストに追加されます。
スーパーバイザーと従業員のランキングの差がゼロ以下の場合は、1 レベル上に移動し、次のレベルのサブツリーに対して上記の比較を実行します。
会社の頭が分析されるまでレベルを上げ続け、パーティーランク合計とゲストリストを印刷します。
実行時間の私の分析はO(n log n -1)、
log n-1- 最下位のサブツリーに降りる時間
n- 比較の最大数
面接で思いついたのですが、何かが足りない気がして仕方がありませんでした。分析と手順は正しいですか?