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

Question

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

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

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

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

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

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

Но, несомненно, есть лучший способ решения этой относительно простой проблемы.

Answer 1

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

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

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

Изменить в ответ на ваш комментарий:

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

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

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

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

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