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

本文关键字：平衡 存储 对象 重叠 标准 算法 是否 | 更新日期: 2023-09-27 18:00:14

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

{ 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 个桶(彼得、雷蒙德、温斯顿(和一个 2 个(达纳、伊贡(。

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

  1. 按开始时间对列表进行排序
  2. 创建空存储桶
  3. 从列表中选择第一个用户
  4. 对照存储桶中的所有用户检查该用户
  5. 如果该用户与存储桶中的每个人重叠，请将该用户放入其中并将其从列表中删除
  6. 如果存储桶具有理想的大小 (4(，或者如果我循环并检查同一用户三次以上，请关闭存储桶并创建一个新的空存储桶

这适用于前几个存储桶，但会导致只有 2 人的存储桶可以更好地组合。

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

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

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

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

tl;dr： win 的动态编程 (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。

根据您的问题，我可能会做一些事情，例如首先制作一个名为"Person"pr 的类。为此类指定"名称"、"开始时间"和"结束时间"属性。

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

然后将它们放在某个类型为"人"的有序列表中。(此外，我目前正在将时间存储为双精度。您只需将我拥有的时间的任何小数部分乘以 60/100 即可将它们转换回时间。

后记，您可以列出存储桶列表，如果需要，可以向其添加新存储桶。然后，您根据您定义的阈值对列表进行排序，如果要比较的两个对象基于该阈值重叠，则它们都将进入该存储桶。如果它们不重叠，则移动到下一个存储桶，如果存在重叠，则将其添加到该存储桶，依此类推，直到到达最后一个存储桶。如果您遍历了所有存储桶，但仍然没有重叠，请为该对象创建一个新存储桶。

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);
                }
            }
        }
    }
}

然后，只需添加一个 print 命令即可打印出存储桶列表的每个存储桶中每个对象的名称属性。如果您有任何问题/疑虑，请发表评论，干杯。

您可以修改算法以合并间隔树以加快搜索速度

  1. 按开始时间对列表进行排序
  2. 将项目添加到间隔树
  3. 创建空存储桶
  4. 从列表中选择第一项
  5. 使用间隔树的间隔搜索查找第一个项目的阈值时间内填满存储桶的最早项目
  6. 从列表中删除已分桶的项目
  7. 如果列表为空，请停止，否则转到步骤 4

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

相关文章：