堆叠事件/项目的算法

Question

我正在寻找一个伪甘特图，除了其中的事件可以在同一条线上，只要它们不重叠，就像这样:

               M T W R F S U M T W R F S U M T W R F S U
Category 1:   |Event 1|     |Event 2| |------Event 3--|
                |---------Event 4-----------| |-Event 5-|

我正在寻找一种算法来有效地打包这些事件。我知道我可以使用事件的长度和开始日期来确定重叠，但我希望有某种起点。

出于好奇，我正在研究绕过 SharePoint 2007 中甘特图日历 View 的限制。我们的用户喜欢该 View ，但不希望每行一个任务。

Answer 1

我的第一次尝试是按开始时间/日期对任务进行排序。然后我将它们一次一个地放在第一行，它们的开始时间还没有被占用。我(完全)不确定这会给出最佳结果(即始终使用尽可能少的行数)，但它至少应该是合理的一半。

然而，我对它的思考越多，我就越认为它实际上可能是最佳的。优化问题通常很困难，因为与项目的数量相比，组合的数量增长得非常快。然而，在这种情况下，您并没有真正得到这样的组合爆炸，因为您不能重新排列项目——至少我假设它们的开始时间都是预先设定的，所以它们不能被重新排列。

编辑:明确一点:这里我假设问题仅涉及显示开始时间和持续时间已知的事件时间表，因此优化仅意味着显示数据尽可能“紧凑”。我不是在谈论尝试自己创建日程表(即，试图弄清楚在什么时间安排什么事件)。根据所涉及的限制，这通常是一个更困难的问题。只要你唯一的约束是任务间的依赖性，这就相当容易，但是当你添加诸如最大人力使用和受限资源之类的东西时(例如，任务 X 只能由 A、B 或 C 执行，任务 Y 由 B 执行) 、C 或 D 等)，情况很快变得非常困难。