如何计算两个(价格,时间)数组的价格差≤10的重叠时长？

核心思路 #

利用双指针法遍历两个按时间升序排列的数组，每次聚焦当前两个有效区间，计算重叠部分并判断价格差是否符合条件，累加有效时长。该方法时间复杂度为O(m+n)（m、n为两数组长度），能覆盖所有边界情况。

步骤详解 #

1. 初始化：设置双指针i、j分别指向两个数组起始位置，总时长total初始为0。
2. 遍历有效区间：循环条件为i < len(array1)-1且j < len(array2)-1（单个元素无法形成左闭右开区间，无有效价格时段）。
3. 提取当前区间信息：
   • 对array1，当前区间为[array1[i][1], array1[i+1][1])，价格为array1[i][0]
   • 对array2，当前区间为[array2[j][1], array2[j+1][1])，价格为array2[j][0]
4. 计算重叠区间：
   • 重叠起始时间：max(array1[i][1], array2[j][1])
   • 重叠结束时间：min(array1[i+1][1], array2[j+1][1])
5. 判断并累加有效时长：若重叠起始时间小于结束时间（存在有效重叠），且价格差绝对值≤10，则将时长（结束-起始）累加到total。
6. 移动指针：将指向结束时间更早的区间的指针后移一位，继续处理下一个区间。

代码实现（Python） #

def calculate_overlap_duration(array1, array2):
    total = 0
    i = j = 0
    len1, len2 = len(array1), len(array2)
    
    while i < len1 - 1 and j < len2 - 1:
        # 获取array1当前区间的时间范围和价格
        start1, end1 = array1[i][1], array1[i+1][1]
        price1 = array1[i][0]
        # 获取array2当前区间的时间范围和价格
        start2, end2 = array2[j][1], array2[j+1][1]
        price2 = array2[j][0]
        
        # 计算重叠区间的起止时间
        overlap_start = max(start1, start2)
        overlap_end = min(end1, end2)
        
        # 存在有效重叠且价格差符合要求时累加时长
        if overlap_start < overlap_end:
            if abs(price1 - price2) <= 10:
                total += overlap_end - overlap_start
        
        # 移动到下一个更早结束的区间
        if end1 < end2:
            i += 1
        else:
            j += 1
    
    return total

# 示例验证
array1 = [(10, 1), (5, 2), (7, 4)]
array2 = [(19, 0), (6, 2), (23, 4)]
print(calculate_overlap_duration(array1, array2))  # 输出3

关键边界覆盖 #

• 单个元素数组：无有效区间，直接返回0
• 无重叠区间：重叠起止时间相等，不累加时长
• 区间完全包含：处理完被包含的区间后，指针移动继续处理剩余部分
• 价格差刚好等于10：符合条件，正常累加时长

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