Алгоритм оптимального планирования времени для приложения управления событиями

Question

Я работаю в приложении для управления событиями в реальном мире, где события планируются в зависимости от наличия места проведения, ни одно из событий не должно конфликтовать.Какова наилучшая возможность вставить следующее значение.

Пример: Предположим, что Событие 1 происходит между 9 и 9:30 в комнате А Событие 2 происходит между 9 и 10:00 в комнате Б Событие 3 может начинаться в 9:30 в комнате A, так как он свободен после 9:30 и т. Д. ......

Какой алгоритм я могу использовать?

Примечание: это не алгоритм планирования ЦП

Спасибо:)

Answer 1

Я бы пошел с жадным подходом.

1. Сортировка всех событий по времени начала
2. Для каждого объекта:
   1. T = самое раннее время
   2. Найдите самое раннее событие в или после T и запланируйте его для этого места. Удалить это событие из списка.
   3. Обновить T до времени окончания этого события

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