Доказательство жадного алгоритма для выбора заявок

  • Автор темы BredoZavR
  • Дата начала
B

BredoZavR

#1
Задача о заявках (расширенная)
Удовлетворить все заявки в наименьшее количество аудиторий.
Алгоритм написан, реализован
Состоит в том, что заявки сортируются не как при обычном Greedy Activity Selector по окончании, а по количеству совместных с ними (по возрастающей)

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

Надо будет код, вставлю