Есть ли недостатки в моем алгоритме Greedy?

Question

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

• Они набор сотрудников
• Каждый сотрудник имеет одну рабочую смену, которая представляет собой один интервал времени в течение недели. Смены сотрудников имеют возможность дублирования.
• Подгруппа сотрудников формирует группу по надзору.
• У группы по надзору есть свойство, что на каждый момент смены каждого сотрудника также работает надзорный орган.

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

Теперь мой жадный алгоритм для решения этой проблемы. Предположим, есть список сотрудников:

  While(there are employee's who aren't supervisors and are not removed )
      Choose first employee working with longest work shift to be supervisor. 
      Remove any employee whos finish time is less than the current supervisor finish time.

      If(supervisor shift is ending)
         Turn employee whos shift interests with supervisor shift,
         with longest work time remaining into a supervisor as well.
      end if
  End while

      return list of supervisors

Будет ли это работать? И действительно ли это вернет наименьшую возможную группу руководителей? Я не уверен, что это лучший способ сделать это.

Спасибо

Answer 1

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

Давайте представим, что ваш алгоритм не дает оптимального решения. Это означает, что существует сотрудник E0 кто мог бы заменить как минимум двух сотрудников E1 а также E2 которые были назначены руководителями в течение двух последовательных интервалов. Это означает, что E0Сдвиг начался, по крайней мере, еще E1с, и закончилось так поздно или позже, чтоE2"S. Однако, если бы это было правдой, ваш жадный алгоритм выбрал бы E0 над E1 быть руководителем, что является противоречием. Это означает, что ваш алгоритм находит оптимальное решение проблемы.