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

Question

我得到了一份会谈(技术会谈)列表及其各自的持续时间，我必须以最不浪费时间的方式组织这些会谈。

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

上午 session 从上午 9:00 开始，到中午 12:00 结束(午餐)中午之后 下午 1:00 开始，下午 4:00 结束

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

它的工作方式与我预期的 o/p 相同，但我不确定这是否是最佳方式。关于我在某个方向上还可以做什么或思考的任何想法？

Answer 1

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

举个简单的例子，假设您只有一个 session ，有 3 个小时的可用时间。有四场演讲，一场持续 2.5 小时，其他一场持续 1 小时。您的算法将选择第一个谈话而不会为任何其他人留出空间，从而导致半小时的停机时间。但最佳解决方案当然是选择三个 1 小时的讲座，零停机时间。

与常规背包问题不同，据我所知，多背包问题很棘手。这是一个 PDF 文件，可能会提供一些信息 ( link )，但我将维基这个答案，任何有简洁明了答案的人都可以随意编辑。