2

Делается проект под резервацию комнат / столиков. Суть этого проекта - создавать брони, записывать в бд, показывать их на фронте на временных линиях. Причем, резервации не закрепляются за каким-то конкретным столиком / комнатой, есть только ограничение по количеству используемых столиков / комнат одновременно.

Условно, в один временной слот может максимально быть использовано только 15 столиков.

Представим, что мы записали в базу 13 бронирований столиков с 13:30 до 15:30, и 13 бронирований с 16:00 до 17:00. В максимально оптимизированном формате мы сможем садить людей таким образом, чтобы использовать только 13 столиков, так как пересечений по бронированию нет.

На текущий момент есть бэк на ноде, который кидает sql запрос в mysql, чтобы вытащить все брони, которые имеют пересечения с желаемым временным промежутком, который мы хотим забронировать.

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

Представим, что мы хотим создать бронирование с 15:00 до 16:30.

Улетает вышеописанный запрос в базу данных и таблица возвращает 26 строк. Именно поэтому просто смотреть количество пересечений не вариант.

Каким образом можно алгоритмически рассчитывать самую оптимальную посадку людей для самого оптимального использования столиков?

3
  • 1
    Простое решение: рабочее время разбивается на отрезки по 15 минут. Для каждого отрезка запоминается количество занятых столиков. Эту структуру легко обновлять и легко запрашивать доступен ли столик в течение определённого периода времени. Единственное ограничение - столики бронируются на период времени начинающийся и заканчивающийся во времена кратные 15 минутам. Для полных суток вам понадобится 96 записей. 6 авг 2022 в 17:10
  • 1
    Забыл добавить что оптимальную рассадку рассчитывать не нужно. Клиенты просто получают свободные столики когда они приходят. Никакого специального алгоритма рассадки не нужно. 6 авг 2022 в 17:14
  • @StanislavVolodarskiy Неплохая идея, спасибо! 6 авг 2022 в 17:35

1 ответ 1

2

Это достаточно классическая задача о выборе заявок. Решается "жадным алгоритмом". "Надежный шаг" для этого случая говорит, что существует самое оптимальное покрытие, в котором правый конец интервала минимален (т.е. надо брать тот интервал, который раньше заканчивается).
Это безопасный и локально оптимальный шаг (если возьмем другой интервал, то он не пересчет меньшее количество интервалов).

Поэтому начинайте с того, что распределяйте сначала столики тем, кто раньше уйдет.
После выполнения этого шага вы получите подзадачу, подобную исходной. Действуйте так далее для всех столиков.

Алгоритм (передавайте в задачу совокупность интервалов - начало и конец):
отсортировать 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

1
  • 1
    Да, я сейчас пытаюсь вникнуть в этот алгоритм, спасибо! 6 авг 2022 в 16:13

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.