Пересекающиеся заявки на помещение: как выбрать совместимый набор

Выбирается план предложений, а не отменяются обещания

Рассмотрим один обычный переговорный зал. Руководитель получил пакет запросов на конкретное время и должен подготовить совместимый набор предложений. Все рассматриваемые запросы ещё не подтверждены; договорённости, обязывающей принять каждый из них или соблюдать очередность поступления, в учебных условиях нет.

Цель заранее согласована: выбрать максимально возможное число заявок, каждая имеет одинаковый вес один. Это не расчёт выручки, прибыли, длительности занятости или справедливости между клиентами. Если правила бизнеса требуют иного порядка, подменять его максимумом количества нельзя.

Результат расчёта не отправляет отказ и не подтверждает бронь автоматически. Он показывает допустимый набор для следующего согласованного действия. Уже подтверждённые записи защищены до начала выбора и не участвуют в конкурсе с новыми запросами.

Полный занятый интервал важнее времени встречи

У каждой заявки фиксированы начало и конец использования зала. После использования требуются ещё десять минут уборки; они уже входят в указанный ниже занятый интервал. Дополнительной подготовки до начала и отдельного перехода между заявками в примере нет. Нужный персонал для уборки доступен в каждом таком интервале, других общих ресурсов не требуется.

Две заявки совместимы, если занятый интервал одной заканчивается не позже начала другой. Равенство разрешено: окончание уборки в 10:00 позволяет следующей встрече начаться в 10:00. Повторно добавлять те же десять минут к уже расширенному интервалу нельзя.

Проверка сотрудников, помещения, оборудования и разных фаз разобрана в материале о ресурсах и буферах записи. Здесь эти условия сведены к одному заранее проверенному ресурсу и фиксированным интервалам. Если нужна ещё одна общая комната или один сотрудник, который не успевает между встречами, наша простая модель недостаточна.

Сначала исключите конфликт с подтверждённой бронью

Все часы и заявки вымышлены, относятся к одному местному дню и одному часовому поясу без перевода часов. Зал уже подтверждённо занят с 13:00 до 14:00, включая все необходимые операции этой брони. Её нельзя сдвинуть ради нового набора.

Поступили шесть неподтверждённых запросов. После названия указаны время использования и затем полный занятый интервал:

• A: встреча 09:00–11:50; с уборкой зал занят 09:00–12:00.
• B: встреча 09:10–09:50; занято 09:10–10:00.
• C: встреча 10:00–10:40; занято 10:00–10:50.
• D: встреча 10:50–11:30; занято 10:50–11:40.
• E: встреча 12:00–12:50; занято 12:00–13:00.
• F: встреча 12:55–13:20; занято 12:55–13:30.

F конфликтует с уже подтверждённым интервалом 13:00–14:00, поэтому в текущий набор предложений не входит. Это объяснение невыполнимости указанного времени, а не разрешение удалить заявку или отправить клиенту отказ. Возможный другой слот требует отдельного обсуждения и нового запроса.

E заканчивает уборку ровно на 13:00 и по заданному правилу не конфликтует с подтверждённой бронью. После проверки остаются A, B, C, D и E. Именно среди них выбирается совместимый набор.

Раннее начало выбирает две заявки, раннее окончание — четыре

Если сначала выбрать заявку с самым ранним началом, получится A. Она занимает зал до 12:00 и перекрывает B, C и D. После неё совместима E, поэтому набор A + E содержит две заявки.

Для цели максимального количества на одном ресурсе с фиксированными интервалами используется другой порядок: взять допустимую заявку с самым ранним окончанием, оставить совместимые последующие и повторить. В учебных материалах MIT 6.046J, Lecture 1 приведены постановка и доказательство этого правила для максимального числа непересекающихся запросов.

1. Первой заканчивается B на 10:00. После её выбора A несовместима.
2. Из оставшихся подходящих раньше заканчивается C на 10:50. Её начало 10:00 совпадает с освобождением после B.
3. Далее D занимает 10:50–11:40.
4. После D подходит E: 12:00–13:00. Промежуток 11:40–12:00 остаётся свободным.

Речь об окончании полного занятого интервала, а не только встречи. Мы не выбирали самую короткую заявку и не сокращали A. Длительности и запрошенное время всех клиентов остались прежними.

Проверьте максимум, а не только отсутствие пересечений

Четыре совместимые заявки уже найдены. Чтобы назвать их максимумом в нашем маленьком примере, нужно исключить более крупный набор. После удаления F есть пять кандидатов; единственный набор из пяти содержит A вместе с B, C и D, что невозможно из-за пересечения.

Можно рассмотреть случаи ещё точнее. Любой набор с A не содержит B, C или D и может добавить только E: максимум две заявки. Без A остаются четыре кандидата B, C, D, E, и все они совместимы. Значит, максимум равен четырём, а выбранный набор его достигает. Прямой перебор всех 32 подмножеств этих пяти кандидатов даёт тот же результат.

Правило раннего окончания не является универсальным правилом продаж. Если длинная A имеет иной вес или приоритет, максимальное количество и максимальная выбранная ценность могут требовать разных наборов. Материал MIT отдельно разбирает взвешенную постановку, для которой этот простой выбор уже не обеспечивает общий оптимум.

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

Граница пакета и подтверждение меняют доступность

Расчёт предполагает известный пакет заявок. Он не обещает оптимального результата при неизвестных будущих поступлениях. Если сначала подтвердить A, а B, C и D придут позже, отменять A ради более красивого максимума нельзя. Новый расчёт должен считать её защищённой бронью.

Укажите момент снимка и список включённых запросов. Для каждого сохраняйте идентификатор, запрошенное использование, занятый интервал, основание буфера, статус подтверждения и причину исключения. Не смешивайте «клиент запросил», «время предварительно предложено» и «бронь подтверждена».

Перед фактическим подтверждением выбранного набора ещё раз проверьте календарь. Если другой сотрудник успел занять часть времени, прежний расчёт устарел. Способ резервирования и проверки версии зависит от системы, но две конкурирующие операции не должны подтвердить один зал на пересекающееся время.

Если подтвердились только B и C, сохраняйте именно этот результат. Нельзя считать D и E принятыми по одному успешному действию или повторно отправлять весь пакет без проверки. Заявки, не вошедшие в текущий набор, остаются видимыми со своим следующим согласованным шагом.

Как применять выбор без подмены цели

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

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

Для SABSUS обсудите процесс через управление заказами и задачи. Хранение занятых интервалов, статусов предложения и подтверждения, контроль конфликтов и автоматический подбор набора нужно проверить в выбранной конфигурации. Статья не предполагает встроенный оптимизатор интервального расписания.

Приёмочный лист и вывод

• Текущая бронь 13:00–14:00 защищена до выбора.
• F исключается из текущего плана из-за конфликта с ней; E допускается на точной границе.
• Десять минут уборки включены в занятый интервал один раз.
• A + E дают две новые заявки, B + C + D + E — четыре.
• Максимум четыре подтверждён рассмотрением всех возможных случаев.
• Цель по количеству не выдаётся за максимум выручки или универсальный порядок обслуживания.
• Расчёт предложения не равен факту подтверждения и не отменяет прежних обещаний.

Вывод: для неподтверждённого пакета фиксированных запросов можно искать самый большой совместимый набор. Но сначала нужно защитить существующие брони, включить полный занятый интервал и явно согласовать цель. Только в этой узкой постановке правило раннего окончания отвечает на поставленный вопрос.

Источник: MIT OpenCourseWare: Lecture 1, Overview and Interval Scheduling и связанные конспекты. Проверено 12 октября 2026 года. Времена, заявки и доказательство для данного набора являются оригинальным учебным примером редакции.