Алгоритмы

[alex-ac]

Написать алгоритмы, для следующих задач:

• Установка времени события так, чтобы оно не конфликтовало с другими событиями людей, участвующих в нем.
• Отбор людей для регулярно повторяющегося события.

Вводятся дополнительные сущности в алгоритмах:

traits - ограничения событий по времени.

traits ::= traits_list "\" traits_list
traits_list ::= {trait}
trait ::= "("datetime"|"datetime")"
datetime ::= year"-"month"-"day" "hour":"min":"sec

до "" - интервалы времени, в которые событие может проходить, после - интервалы, в которых событие проходить не может.

В итоге событие располагается на множестве:

U ⋂ ( A_1 ∪ A_2 ∪ ... ∪ A_i) \ D_1 \ D_2 \ ... \ D_j

A_1 ... A_i - интервалы до "", D_1 ... D_j - интервалы после "".

В lua представляется таблицей

traits = {
 ["allow"] = {
  {["from"] = timestamp, ["to"] = timestamp},
  {["from"] = timestamp, ["to"] = timestamp}
 },
 ["deny"] = {
  {["from"] = timestamp, ["to"] = timestamp},
  {["from"] = timestamp, ["to"] = timestamp}
 }
}

Функции:

algorithms.parse_traits(traits) -- перевести из строки в таблицу
algorithms.make_traits(traits) -- обратное преобразование
algorithms.optimize_traits(traits) -- оптимизовать интервалы
         -- (убрать пересечения, по возможности избавиться от deny ограничений)

[alex-ac]

lua модуль task_system реализует универсальный алгоритм по теории расписаний. Для работы необходимо создать задачи, ресурсы и процессоры (процессор - ресурс необходимый для выполнения любой задачи, но притом только один), а также порядок назначения событий (тут вся соль).

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

Поясню:
К примеру помещения можно считать процессорами (для проведения лекции нужна аудитория, притом только одна), ресурсами - лектора и студентов (они должны быть на событии, но их много).