c# - 是否有标准算法将重叠对象平衡到桶中？

Question

我有一堆用户，有给定的开始和结束时间，例如:

{ Name = "Peter", StartTime = "10:30", EndTime = "11:00" },
{ Name = "Dana", StartTime = "11:00", EndTime = "12:30" },
{ Name = "Raymond", StartTime = "10:30", EndTime = "14:00" },
{ Name = "Egon", StartTime = "12:00", EndTime = "13:00" },
{ Name = "Winston", StartTime = "10:00", EndTime = "12:00" }

我想根据它们重叠的时间(基于可配置的阈值，例如，它们至少需要重叠半小时)将它们放入桶中。我希望桶最好有 4 件大，但 2-5 之间的任何范围都是可以接受的。

在上面的示例中，没有 4 个人匹配，所以我有 3 个(Peter、Raymond、Winston)和 2 个(Dana、Egon)中的一个桶。

我设计了一个似乎依赖于机会而不是科学的算法原型(prototype):

1. 按开始时间排序列表
2. 创建一个空桶
3. 从列表中选择第一个用户
4. 根据存储桶中的所有用户检查该用户
5. 如果该用户与桶中的每个人重叠，则将该人放入其中并将其从列表中删除
6. 如果桶的大小合适 (4)，或者如果我循环检查同一个用户超过 3 次，请关闭桶并创建一个新的空桶

这对于前几个桶很有效，但会导致只有 2 个人的桶可以更好地组合。

我可以更改算法以从列表中删除所有理想桶并重新洗牌并尝试更多，但我觉得这应该是一个常见问题 - 这就像 worker 的轮类分配，或者可能是 knapsack problem .

有人知道这类问题的标准算法吗？

(标记组合学因为我认为这是它适用的数学领域，如果错误请纠正我)

Answer 1

tl;dr: 获胜的动态规划(O(sort(n)) 时间)。

首先，请注意按开始时间顺序连续分桶是可以的。

命题(碎片整理)让 a, b, c, d 是不同的用户，这样 StartTime(a) ≤ StartTime(b) ≤ StartTime( c) ≤ StartTime(d)。如果 X 和 Y 是有效的桶使得 a, c ∈ X 和 b, d ∈ Y，那么X - {c} ∪ {b} 和 Y - {a} ∪ {d} 也是有效的桶。

我只知道如何通过繁琐的案例分析来证明这一点(略)。

结果是，您可以假装将段落分成几行，其中“段落”是按开始时间顺序排列的用户列表，而每一“行”都是一个桶。由于 Knuth 和 Plass 提出了一种优化换行的算法，其中对给定行的惩罚或多或少是一个任意函数。例如，您可以将 4 个桶的成本设为 0，将 3 个桶设为 1，将 2 个桶设为 2，将 1 个桶设为 100。