是否有一种标准算法来将重叠的对象平衡分配到桶中？

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个人的桶可以更好地组合。

我可以更改算法，从列表中删除所有理想的桶并重新洗牌并再次尝试，但我觉得这应该是一个常见的问题 - 就像工人的转移任务或背包问题一样。

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

（标记组合数学，因为我认为这适用于数学领域，如果我错了请纠正我）

- Michael Stum

---

您想要根据仅有的30分钟（阈值）重叠来排序桶，还是要根据谁的重叠最多来排序？ - Orren Ravid

@OrrenRavid 任何重叠都可以。我们可能会调整最小重叠时间（例如，最少60分钟），但与重叠180分钟的人相比，重叠60分钟的人同样出色。 - Michael Stum

我认为使用区间树会很好。https://zh.wikipedia.org/wiki/区间树 - jamesSampica

我写了一个区间树程序。它的算法并不像应该的那样简洁，但基本上就是下面的答案。 - Orren Ravid

Answer 1

简短概述：动态规划胜利（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。

- David Eisenstat

Answer 2

根据您的问题，我可能会首先创建一个名为 "Person" 或相似的类。给这个类添加 "姓名"、"开始时间" 和 "结束时间" 等属性。

class Person
{
     public string name;
     public double start_time;
     public double end_time;
}

然后将它们放入一些类型为Person的有序列表中。(我目前将时间存储为double。您可以通过将我拥有的任何小数部分乘以60/100来将它们转换回时间。)

之后，您可以制作一个Bucket列表，如果需要，可以向其中添加新的Bucket。然后根据您定义的阈值对列表进行排序，如果正在比较的两个对象基于该阈值重叠，则这两个对象都进入该Bucket。如果它们不重叠，则移动到下一个Bucket，如果那里有重叠，则将其添加到该Bucket中，依此类推，直到达到最后一个Bucket。如果您已经遍历了所有的Bucket，仍然没有重叠，则为该对象创建一个新的Bucket。

class MainFunc
{    
    static void Main(string[] args)
    {    

         //makes a function to check if 2 values overlap over a threshold
         //st stands for start time and et stands for end time

         public bool IsWithinThreshold(double st1, double st2, double et1, double et2)
         {
             double threshold = .5;
             if(st1 >= et2 || st2 >= et1)
             {
                 return false
             }
             else
             {
                 if(st1+threshold <= et2 && st1+threshold <= et1 || st2+threshold <= et1 && st2+threshold <=et2)
                 {
                     return true;
                 }
                 else
                 {
                     return false;
                 }
             }
         }           
        // makes objects of type Person with attributes of name, start time, and end time

        Person Peter = new Person();
        Peter.name = "Peter"
        Peter.start_time = 10.5
        Peter.end_time = 11.0

        Person Dana = new Person();
        Dana.name = "Dana"
        Peter.start_time = 11.0
        Peter.end_time = 12.5

        Person Raymond = new Person();
        Raymond.name = "Raymond"
        Raymond.start_time = 10.5
        Raymond.end_time = 14.0

        Person Egon = new Person();
        Egon.name = "Egon"
        Egon.start_time = 12.0
        Egon.end_time = 13.0

        Person Winston = new Person();
        Winston.name = "Winston"
        Winston.start_time = 10.0
        Winston.end_time = 12.0

        //puts objects of type Person into an unordered list

        List<Person> people = new List<Person>();
        people.Add(Peter);
        people.Add(Dana);
        people.Add(Raymond);
        people.Add(Egon);
        people.Add(Winston);

        //sets up a list of lists of People (Buckets in our case)

        List<List<Person>> Buckets = new List<List<Person>>;

        //sets up an intial Bucket and adds the first person on the list to it

        List<Person> Bucketinitial = new List<Person>;
        Bucketinitial.add(people[0]);


        for(var i = 1; i < people.Count; i++)
        {
            for(var j = 0; j< Buckets.count; j++)
            {
                //sets a checker to make sure that all objects in a given Bucket overlap with the person we are checking

                bool overlap = true;

                for(var k = 0; k< Buckets[k].count; k++)
                {
                overlap = overlap & IsWithinThreshold(people[i].start_time,Buckets[j][k].start_time,people[i].end_time,Buckets[j][k].end_time)
                }

                if (overlap == true)
                {
                    Buckets[j].add(people[i])
                }

                //if all the objects in a bucket don't overlap with the person...
                //... make a new Bucket with that person
                else
                {
                    List<Person> NewBucket = new List<Person>;
                    NewBucket.add(people[i]);
                    Buckets.add(NewBucket);
                }
            }
        }
    }
}

然后只需添加一个打印命令，以打印桶列表中每个对象的名称属性。如果您有任何问题/疑虑，请留下评论，谢谢。

- Orren Ravid

---

请注意，我的空格可能有误，因此在将代码放入您喜欢的编译器时，请确保重新排版，以便您拥有完美的制表符代码行。 - Orren Ravid

Answer 3

你可以修改算法，加入区间树来加速搜索。

1. 按StartTime排序列表
2. 将项目添加到区间树中
3. 创建一个空桶
4. 从列表中选择第一个项目
5. 使用区间树的区间搜索查找填充一个桶内与第一个项目在阈值时间内最早的项目
6. 从列表中删除桶内的项目
7. 如果列表为空，则停止，否则转到步骤4

基本上，您使用区间步长（由可配置的阈值给出）从左向右移动，同时使用区间树快速查询最接近的项目。

- dpmcmlxxvi