2

次の問題を解決するために使用できる一般的なアルゴリズムはありますか？

与えられた：

背景：1か月。0から1000のイベントがあります（実際には任意の数）。各イベントには開始日と終了日があります。イベントは一度に1つずつ部屋で行われます（重複はありませんが、結果として生じるイベントは互いに終了日と開始日を共有できます）。部屋の数は無制限です。

課題：毎月のイベントを開催するために必要な部屋の数が最小限に抑えられるように、イベント用の部屋を割り当てます。

完全なソリューションは高く評価されていますが、私はあらゆる方向性、賢いアイデアを探しています。

class Event: 
- int Id;
- DateTime StartDate; 
- DateTime EndDate

class Allocation:
- int EventId
- int RoomId

だから私は探しています：

// roomIds is Enumerable.Range(1, int.MaxValue)
IEnumerable<Allocation> GetAllocations(IEnumerable<Event> events, IEnumerable<int> roomIds, int year, int month)
{
  ...
}
4

2 に答える 2

4

すべてのイベントを「開始」と「終了」というラベルの付いた2つの時点に分割し（元のイベントへのバックポインターを保持）、すべての時点を時間どおりに並べ替えます。

次に、ポイントを（上記で定義された順序で）調べ、各「開始」に最初の空き番号を割り当て、各「終了」に関連する番号を解放します。

例：

イベント：午前9時〜午後5時、午前9時〜午後2時、午後5時〜午後6時、午後3時〜午後6時

ソートされた時点のテーブル：

（9AM開始イベント1）、（9AM開始イベント2）、（2PM終了イベント2）、（3PM開始イベント4）、（5PM終了イベント1）、（5PM開始イベント3）、（6PM終了イベント3）、（6PM終了イベント4）

処理：

(9AM start event1) - assign room 1 to event1
(9AM start event2) - assign room 2 to event2
(2PM end event2) - free room 2
(3PM start event4) - assign room 2 to event4
(5PM end event1) - free room 1
(5PM start event3) - assign room 1 to event3
(6PM end event3) - free room 1
(6PM end event4) - free room 2
于 2013-02-14T15:25:14.953 に答える
0

これは、学部生のときに受講したアルゴリズムクラスからほぼ逐語的です。最も早い開始時間と最も短い期間に基づいて部屋を割り当てる欲張りアルゴリズムが最適です。この最適性の証明は、教授が読者をばかにしないようにするための演習として残されています。:)

于 2013-02-15T14:56:18.690 に答える