寻找两个区间之间交集的最佳算法

本文关键字：最佳 算法 之间 区间 两个 寻找 | 更新日期: 2023-09-27 18:09:57

我在数据库中有一个名为Control的表:

表结构:

Id | Name | MinValue (decimal) | MaxValue(decimal)

我对这个表有一些限制，其中一个限制是:没有交集

示例:如果表中有如下值:

第一行:1 | Test1 | 1.3 | 2.5//有效的
row2: 2 | Test2 | 3.3 | 4.5//有效的
row3: 3 | Test3 | 5 | 6//有效的

现在如果我想添加一条新记录，它不能与任何其他行相交

示例:

row4: 4 | Test4 | 5.1 | 10//无效因为槽位从5到6是预留的
row5: 5 | Test5 | 1.0 | 1.4//无效因为槽位从1.3到2.5是预留的

我正在使用这段代码，它工作得很好，但我想知道是否有更好的解决方案和更有效的:

var allRows = db.Control.ToList();
var minValue = control.MinimumValue;
var maxValue = control.MaximumValue;
bool flag = true;
foreach(var row in allRows)
{
    for(var i = minValue; i <= maxValue && flag ; i = decimal.Add( i , (decimal) 0.01))
    {
        if(i >= row.MinimumValue && i <= row.MaximumValue)
        {
            flag = false;
            min = row.MinimumValue;
            max = row.MaximumValue;
            break;
        }
    }
}
if (flag)
{
    //add
}
else
{
    //intersection
}

有什么建议吗

寻找两个区间之间交集的最佳算法

我认为这是O(LogN)的问题…

按起始值排序。
对于任意i

的有效列表s[i].end < s[i+1].start

插入新段时，找到它的位置(开始最接近(但较小)的位置)，称为i 

if((seg[i-1].end < new.start) && (seg[i+1].start > new.end)) 
    //OK to insert
else
    // intersect

假设这是您要添加的对象:

var control = new Control()
{
    Name = 'name',
    MinValue = 5,
    MaxValue = 6
};

你可以这样做:

var biggerThanMinValue = db.Control.Count(x => x.MinValue >= control.MinValue) != 0;
var biggerThanMaxValue = db.Control.Count(x => x.MaxValue >= control.MaxValue) != 0;
if (!biggerThanMinValue && !biggerThanMinValue)
{
    db.Control.Add(control); // or whatever your add operation is
}

通过这样做，您:

  • 不将整个表加载到内存中->根据时间、流量和内存获得性能
  • 让数据库使用它的数据结构/算法来验证项目可以被添加(数据库应该能够优化这个请求)->另一个性能增益(cpu +时间)
  • 有更清晰的后台代码
  • 有更少的代码测试

编辑:我想你也可以要求数据库按min/max值对表进行排序，然后进行一些验证(1或2 if)，但第一种方法更好。

相关文章：