每天早上 9 点到下午 5 点，我应该至少有一个人在工厂监督 worker ，确保没有任何问题。
目前有 n 位求职者，他们每个人都可以在时间 si 到时间 ci 之间工作，i = 1, 2, ..., n。
我的目标是尽量减少两个以上的人同时看守 worker 的时间。
(应聘者的可用工作时间能够涵盖上午9点至下午5点的时间段。)
我已经证明在任何瞬间最多需要两个人来满足我的需求，但我应该如何从这里得到最终的解决方案？
找到只有一个人可以胜任这份工作的时间段并保留他们是我的第一步，但找到下一步是让我烦恼的......。
算法必须在多项式时间内运行。
欢迎任何提示(可能是某种类型的数据结构？)或引用。非常感谢。
最佳答案
我认为你可以通过解决子问题用动态规划来做到这一点:
What is the minimum overlap time given that applicant i is the last worker and we have covered all times from start of day up to ci?
将此值称为最小重叠时间成本(i)。
您可以通过考虑案例来计算 cost(i) 的值:
- 如果 si 等于一天的开始，则 cost(i) = 0(不需要重叠)
- 否则，考虑所有以前的申请人 j。将 cost(i) 设置为 cost(j) + i 和 j 之间的重叠的最小值。也将 prev(i) 设置为达到最小值的 j 的值。
然后，对于所有 k 值，成本 (k) 的最小值将给出您问题的答案，其中 ck 等于一天的结束时间。您可以通过使用 prev 的值进行回溯来计算出正确的人选。
这给出了一个 O(n^2) 算法。
关于algorithm - 集合覆盖概率的变体(可能是事件选择概率)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27655256/