c# - 活动选择。这样做的最佳方法是什么

Question

我得到了一份会谈（技术会谈）的清单，其中包含各自的持续时间，我必须以最不浪费时间的方式组织这些会谈。

他们的谈话没有开始时间和结束时间，并且每个谈话都独立于其他谈话，因为任何谈话都可以随时发生。

上午 9:00 开始，12:00 结束（午餐） 中午 1:00 开始，4:PM 结束

到目前为止，我一直在做的是我已经按持续时间降序对会谈进行排序，然后将它们逐个放入会话 1。

它的工作原理与我得到预期的 o/p 一样，但我不确定这是否是最佳方法。关于我在某个方向上还能做什么或想什么的任何想法？

Answer 1

这是多背包问题的一个实例，您描述的算法（贪心算法）并不总是会产生最佳结果。

举个简单的例子，假设您只有一个会话，有 3 小时可用。有四场讲座，一场持续 2.5 小时，其他每场 1 小时。您的算法将选择第一个谈话并且没有空间容纳任何其他人，给您半小时的停机时间。但最佳解决方案当然是选择三个 1 小时的会谈，让停机时间为零。

与常规背包问题不同，据我所知，多背包问题很棘手。这是一个可能会有所启发的PDF（链接），但我会在wiki上找到这个答案，任何有一个简洁的答案的人都应该随时编辑。