是否有标准算法来将重叠对象平衡到存储桶中？

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)之一.

我已经制作了一个似乎依赖于机会而不是科学的算法原型:

1. 按StartTime排序列表
2. 创建一个空桶
3. 从列表中选择第一个用户
4. 针对存储桶中的所有用户检查该用户
5. 如果该用户与存储桶中的所有人重叠,请将该人员放入其中并将其从列表中删除
6. 如果铲斗具有理想的尺寸(4)或者如果我循环并且检查同一个用户超过三次,请关闭铲斗并创建一个新的空铲斗

这适用于前几个桶,但导致只有2个人可以更好地组合的桶.

我可以更改算法以从列表中删除所有理想的桶并重新洗牌并尝试更多,但我觉得这应该是一个常见问题 - 它就像工人的轮班分配,或者背包问题.

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

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

Answer 1

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

\n\n

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

\n\n

命题（碎片整理）：让a, b, c, d成为不同的用户，使得StartTime(a) \xe2\x89\xa4 StartTime(b) \xe2\x89\xa4 StartTime(c) \xe2\x89\xa4 StartTime(d). 如果X和Y是有效的桶，使得a, c \xe2\x88\x88 X和b, d \xe2\x88\x88 Y，那么X - {c} \xe2\x88\xaa {b}和Y - {a} \xe2\x88\xaa {d}也是有效的桶。

\n\n

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

\n\n

结果是，您可以假装将一个段落分成几行，其中 \xe2\x80\x9cparagraph\xe2\x80\x9c 是按开始时间顺序排列的用户列表，每个 \xe2\x80\ x9cline\xe2\x80\x9d 是一个桶。Knuth 和 Plass 有一种用于最佳断线的算法，其中给定线的惩罚或多或少是任意函数。例如，您可以将 4 个桶的成本设为 0，将 3 个桶的成本设为 1，将 2 个桶的成本设为 2，将 1 个桶的成本设为 100。

\n