1

問題: N 人と S スロットがあります。各人は、自分が忙しいスロットのリストを持っています。すべてが空いているスロットを見つけるには、アルゴリズムを見つける必要があります。

複雑さが O(NS) であるアルゴリズムを既に知っています。より良いアルゴリズムが必要です。

最終的に空いているスロットを見つけるために使用できる、さまざまなデータ構造を動的に維持することができます (会議がスケジュールされるたびに更新されます)。

4

4 に答える 4

2

スロットごとにスロットカウンターを保持します。ビジー スロットごとに、そのスロット slotcounter に 1 を追加します。すべての人々の忙しいスロットのために。

すべての人が使用中のスロットを考慮した後もまだゼロであるスロット カウンターは、すべての人が空いているスロットのカウンターです。おそらくO（k）アルゴリズムです。

カウントする代わりに、ビットマスク/ビットセットを設定して、人物 N のビットマスクのビジー状態のすべての位置にビット S を設定することができます。すべての人のビットマスクのビットごとの OR は、すべての空きスロットに対応するゼロのビットを持ちます。

更新: 問題を述べる方法は、人々を追跡する必要はなく、スロット占有率インジケーターの配列を保持するだけです。最初はすべて無料とマークされています。各人のビジースロットを通過すると、適切な占有インジケータがビジーとしてマークされます。完了したら、まだ空いている配列インジケーターのいずれかが答えになります。

于 2012-08-15T18:57:27.520 に答える
0

S がビジーの場合に設定されたビットを使用して、サイズ S のビットマスクを生成します。すべてのビットマスクをビットごとに OR し、設定されていないビットを抽出します。

于 2012-08-15T20:37:22.733 に答える
0

編集：アルゴリズムは、各人のスロットのソートされたリストがあると仮定して機能します

  1. これで、それぞれサイズ S (最大) の N 個のリストができました。このリストをマージソート: http://en.wikipedia.org/wiki/Merge_algorithm
  2. 典型的なマージ ソート (ヒープを使用) は、複雑さ NlogK になります。ここで、N は、すべての「K」リスト内の要素の総数です。ただし、お使いのバージョンの場合、N リストの各要素は 0 から s-1 の間に制限されています。したがって、複雑さも S*log(N) によって制限されます。S 反復によって制限された、最大 'N' のヒープ サイズで N リストを反復処理します。理にかなっていますか？

したがって、全体的な複雑さ = N*log(S) + S*log(N)

これは、元のリストがソートされていることを前提としています。そうでない場合、複雑さは N(SlogS) まで上がります。

于 2012-08-15T19:04:20.720 に答える
-1

解決策がない可能性があることを念頭に置いて、ハンガリーのアルゴリズムが最も近い答えを提供します

于 2012-08-15T20:32:43.373 に答える