Алгоритмически найти самый оптимальный вариант посадки людей в системе бронирования
Делается проект под резервацию комнат / столиков. Суть этого проекта - создавать брони, записывать в бд, показывать их на фронте на временных линиях. Причем, резервации не закрепляются за каким-то конкретным столиком / комнатой, есть только ограничение по количеству используемых столиков / комнат одновременно.
Условно, в один временной слот может максимально быть использовано только 15 столиков.
Представим, что мы записали в базу 13 бронирований столиков с 13:30 до 15:30, и 13 бронирований с 16:00 до 17:00. В максимально оптимизированном формате мы сможем садить людей таким образом, чтобы использовать только 13 столиков, так как пересечений по бронированию нет.
На текущий момент есть бэк на ноде, который кидает sql запрос в mysql, чтобы вытащить все брони, которые имеют пересечения с желаемым временным промежутком, который мы хотим забронировать.
Казалось бы, можно просто отправить такой запрос в базу данных, посчитать количество вернувшихся строк и на основании этого принимать решение, давать ли бронь или нет.
Представим, что мы хотим создать бронирование с 15:00 до 16:30.
Улетает вышеописанный запрос в базу данных и таблица возвращает 26 строк. Именно поэтому просто смотреть количество пересечений не вариант.
Каким образом можно алгоритмически рассчитывать самую оптимальную посадку людей для самого оптимального использования столиков?
Ответы (1 шт):
Это достаточно классическая задача о выборе заявок. Решается "жадным алгоритмом".
"Надежный шаг" для этого случая говорит, что существует самое оптимальное покрытие, в котором правый конец интервала минимален (т.е. надо брать тот интервал, который раньше заканчивается).
Это безопасный и локально оптимальный шаг (если возьмем другой интервал, то он не пересчет меньшее количество интервалов).
Поэтому начинайте с того, что распределяйте сначала столики тем, кто раньше уйдет.
После выполнения этого шага вы получите подзадачу, подобную исходной. Действуйте так далее для всех столиков.
Алгоритм (передавайте в задачу совокупность интервалов - начало и конец):
отсортировать n отрезков по правым концам
для всех отрезков в полученном порядке:
если текущий отрезок не пересекает
последний добавленный:
взять его в решение
вернуть построенное решение
Время работы: T(Sort) + O(n) = O(n log n).
Подробно об этом можно посмотреть в курсе: https://stepik.org/course/217/syllabus
А вот и та самая задача в виде лекции:
Обоснование: https://stepik.org/lesson/13238/step/4?unit=3424
Алгоритм: https://stepik.org/lesson/13238/step/5?unit=3424