如何高效判断一组浮点区间能否合并为单一连续区间？

需求是判断输入的随机浮点区间集合能否构成单一连续区间：

• 若连续，返回合并后的完整区间；
• 若不连续，返回所有合并后的独立区间。

示例 #

• 示例1：输入[16.0f, 40.0f], [30.0f, 55.0f], [1.0f, 25.0f]，判定为连续，返回[1.0f, 55.0f]
• 示例2：输入[10.0f, 25.0f], [5.0f, 9.0f], [1.0f, 7.0f], [20.0f, 34.0f]，判定为不连续，返回[1.0f, 9.0f], [10.0f, 34.0f]

当前实现的嵌套循环算法 #

现有代码采用嵌套循环方式实现，但希望得到更高效的优化方案，即使区间数量不多也想优化：

for (int i = 0; i < InIntervalRanges.num(); ++i)
{
    const Interval CurrentRange = InIntervalRanges[i];

    bool bAddedToRange = false;
    for (Interval& AllowedHeight : OutIntervalRanges)
    {
        if (AllowedHeight.Contains(CurrentRange.Min))
        {
            AllowedHeight.Include(CurrentRange.Max);
            bAddedToRange = true;
            break;
        }
        if (AllowedHeight.Contains(CurrentRange.Max))
        {
            AllowedHeight.Include(CurrentRange.Min);
            bAddedToRange = true;
            break;
        }
    }

    if (!bAddedToRange)
    {
        OutIntervalRanges.Add(CurrentRange);
    }
}

if (OutIntervalRanges.Num() > 1)
{
    return false;
}

return true;

说明：Interval类包含Min和Max属性，Contains方法用于判断值是否在区间内，Include方法用于扩展区间以包含指定值。

更高效的实现思路是先排序再合并，时间复杂度从原算法的O(n²)降低到O(n log n)，即使数据量小也能体现出逻辑简洁性和稳定性。

具体步骤 #

1. 排序区间：将所有输入区间按照Min值从小到大排序；
2. 遍历合并：初始化结果列表，依次将排序后的区间与结果列表的最后一个区间对比：
   • 如果当前区间的Min小于等于最后一个结果区间的Max，说明两个区间有重叠或相邻，合并这两个区间（更新最后一个区间的Max为两者Max的较大值）；
   • 如果不满足上述条件，说明是新的独立区间，直接加入结果列表；
3. 判断结果：合并完成后，若结果列表长度为1，则返回该区间并判定为连续；否则返回所有合并后的区间并判定为不连续。

代码实现 #

// 先对输入区间按Min升序排序
InIntervalRanges.Sort([](const Interval& A, const Interval& B) {
    return A.Min < B.Min;
});

TArray<Interval> MergedIntervals;
for (const Interval& Current : InIntervalRanges)
{
    if (MergedIntervals.IsEmpty())
    {
        MergedIntervals.Add(Current);
        continue;
    }

    Interval& Last = MergedIntervals.Last();
    // 检查当前区间是否与最后一个合并区间重叠或相邻
    if (Current.Min <= Last.Max)
    {
        // 合并区间，更新Max为较大值
        Last.Max = FMath::Max(Last.Max, Current.Max);
    }
    else
    {
        MergedIntervals.Add(Current);
    }
}

// 根据合并结果返回对应值和状态
if (MergedIntervals.Num() == 1)
{
    OutIntervalRanges = MergedIntervals;
    return true;
}
else
{
    OutIntervalRanges = MergedIntervals;
    return false;
}

优势对比 #

• 时间复杂度更优：排序占O(n log n)，遍历合并占O(n)，整体远优于原嵌套循环的O(n²)；
• 逻辑更简洁：避免了嵌套循环的复杂判断，减少了边界情况遗漏的可能；
• 稳定性更好：排序后合并的逻辑对所有区间分布场景都能稳定处理，不会出现原算法中可能的漏合并情况（比如原算法只检查当前区间的Min/Max是否被已存在区间包含，若当前区间完全覆盖已存在区间则会出错）。

内容的提问来源于stack exchange，提问作者Phoebe Hesketh