algorithm - 我的贪心算法有缺陷吗？

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 结束。然而，如果这是真的，您的贪婪算法就会选择 E0 而不是 E1 作为主管，这是一个矛盾。这意味着您的算法找到了问题的最佳解决方案。