求提取Pressure数组全局重叠区间的算法实现方案

需求说明 #

给定Pressure类型数组（元素数量可达数百个），需要实现一个函数：

• 返回一个Pressure对象，其Low和Hi为数组所有元素的公共重叠区间
• 若数组元素不存在公共重叠区间（即无交集），则返回Low=0、Hi=0

示例：

• 数组PressuresA的公共重叠区间是11.2-11.4，所有元素都包含该区间，故返回此值
• 数组PressuresB无公共重叠区间，故返回0-0

实现思路 #

1. 计算候选重叠区间：
   • 公共重叠区间的Low必须是所有元素Low的最大值（只有大于等于所有元素的下限，才能被所有区间包含）
   • 公共重叠区间的Hi必须是所有元素Hi的最小值（只有小于等于所有元素的上限，才能被所有区间包含）
2. 验证有效性：
   • 如果候选区间的Low <= Hi，说明存在有效公共重叠区间，返回该区间
   • 如果Low > Hi，说明无公共交集，返回Low=0、Hi=0

代码实现 #

class Pressure
{
    public double Low;
    public double Hi;
}

public static Pressure GetOverlapPressure(Pressure[] pressures)
{
    // 处理空数组的边界情况（可根据需求调整逻辑）
    if (pressures == null || pressures.Length == 0)
    {
        return new Pressure { Low = 0, Hi = 0 };
    }

    // 初始化候选区间为第一个元素的范围
    double maxLow = pressures[0].Low;
    double minHi = pressures[0].Hi;

    // 遍历所有元素，更新maxLow和minHi
    foreach (var p in pressures)
    {
        maxLow = Math.Max(maxLow, p.Low);
        minHi = Math.Min(minHi, p.Hi);
        
        // 提前终止：中途已无交集时无需继续遍历
        if (maxLow > minHi)
        {
            break;
        }
    }

    // 判断并返回结果
    return maxLow <= minHi 
        ? new Pressure { Low = maxLow, Hi = minHi } 
        : new Pressure { Low = 0, Hi = 0 };
}

// 测试示例
public static void Main()
{
    Pressure[] PressuresA = new[]  
    { 
        new Pressure { Low = 10.5, Hi = 16.5 }, 
        new Pressure { Low = 11.2, Hi = 11.4 }, 
        new Pressure { Low = 10.3, Hi = 17.5 }
    };

    Pressure[] PressuresB = new[]  
    { 
        new Pressure { Low = 10.5, Hi = 16.5 }, 
        new Pressure { Low =  8.1, Hi = 10.4 }, 
        new Pressure { Low = 10.8, Hi = 11.3 }
    };

    var resultA = GetOverlapPressure(PressuresA);
    Console.WriteLine($"PressuresA结果：Low={resultA.Low}, Hi={resultA.Hi}"); // 输出：Low=11.2, Hi=11.4

    var resultB = GetOverlapPressure(PressuresB);
    Console.WriteLine($"PressuresB结果：Low={resultB.Low}, Hi={resultB.Hi}"); // 输出：Low=0, Hi=0
}

补充说明 #

• 加入空数组边界处理，可根据业务需求调整逻辑
• 遍历过程中加入提前终止判断，提升大数组的处理效率
• 时间复杂度为O(n)，适用于数百个元素的场景

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