Распределение временных интервалов Алгоритм

Question

Существует общий алгоритм, я могу использовать, чтобы решить следующие задачи:

Дано:

фона: Месяц, который содержит от 0 до 1000 событий (любое число на самом деле). Каждое событие имеет дату начала и окончания. События проводятся в комнатах по одному (без совпадений, однако последующие события позволяют делиться концами и датировать даты друг с другом). Количество номеров не ограничено.

Задача: выделить комнаты для таких мероприятий, чтобы количество комнат, необходимых для проведения ежемесячных мероприятий, было сведено к минимуму.

Хотя полное решение высоко ценится, я ищу любые направления, умные идеи.

---

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) 
{ 
    ... 
} 

Answer 1

Split каждое событие в двух временных точках с меткой «старт» и «конец» (сохраняя обратный указатель на исходное событие), сортировать все точки во времени - разорвать связи, чтобы «конец пришел раньше» начинался с того же времени.

Теперь перейдите по точкам (в порядке, указанном выше), выделив первый свободный номер на каждый «запуск» и освободив связанный номер на каждом «конце».

Пример:

Событие: 9 утра до 5 вечера, 9 утра-2 вечера, 5 PM-6PM, 3 PM-6PM

Сортировано таблицы:

моментов времени

(9 утра начала event1), (9AM старт event2), (2 вечера событие окончания 2), (3 вечера начинают event4), (5 вечера конец event1), (5 вечера начать event3), (6 вечера конец event3), (6 вечера конец event4)

Обработка:

(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 

Answer 2

Это почти дословно из класса Алгоритмы, которые я использовал во время моего обучения. Наилучшим является жадный алгоритм, выделяющий комнаты на основе раннего времени начала и кратчайшей продолжительности. Доказательство этой оптимальности оставлено в качестве упражнения, чтобы профессор не заваливал читателя. :)