Ищете математическое решение этой небольшой задачи планирования

Question

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

1. Встреча может быть запланирована только в помещении с емкостью, равной или большей, чем его посещаемость.
2. Если есть лишние номера, встречи должны быть запланированы так, чтобы максимально возможный номер оставался незапланированным.
3. Встреча с более широкой посещаемостью не должна планироваться в меньшем помещении, чем встреча с меньшей посещаемостью.
4. Очевидно, мы должны выяснить, невозможно ли запланировать данные собрания в данных комнатах.

Можем ли мы прийти к графику эффективно? Один прогон был бы хорош, некоторые отступники в порядке, но единственный вариант, который я могу получить для работы (грубый алгоритм плюс динамическое извержение нарушений правила 3) медленнее, чем хотелось бы.

Этот вопрос не так прост, как кажется! Наивные линейные подходы не в состоянии, по крайней мере один критерий:

1. Мы можем отсортировать каждый список от высокого до низкого и начать спаривание самую большую комнату к крупнейшему сессии, мы приедем с решением любое время суток возможно, но у нас будут как можно меньше комнат, а не самые большие. (Рассмотрите случай заседаний 10 и 15 человек, запланированных на 200, 30 и 20 человек.)

2. Мы можем сортировать список встреч от высокого до низкого, а затем спуститься вниз, пытаясь найдите самую маленькую комнату, которая достаточно велика, чтобы содержать эту встречу. Но иногда это приведет к тому, что большая комната будет назначена на меньшую встречу. (Рассмотрим планирование 40 и 30 личных встреч в 40 и 80-местных номерах.)

Но, конечно, есть лучший способ решить эту сравнительно простую задачу.

Answer 1

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

Насколько я могу видеть, что отвечает всем вашим критериям:

1. Проверить
2. Это должно следовать непосредственно из того, что мы всегда выбрали наименьший номер возможного
3. Поскольку мы отсортирован Встречаясь с низкой посещаемостью и высокой посещаемостью, мы никогда не будем проводить большую встречу в маленькой комнате.
4. Если мы дойдем до конца списка номеров до окончания списка встреч, не удалось найти расписание.

Редактировать в ответ на ваш комментарий:

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

Пройдите список номеров и список незапланированных встреч от наивысшего до низкого.

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

Если текущая встреча не подходит в текущей комнате: эта встреча не может быть запланирована. Удалите собрание из списка и попробуйте следующую встречу (в той же комнате).

Повторяйте до тех пор, пока список незапланированных встреч пуст.