如何开发Python算法找出二维数组中的缺失区间？

需求说明 #

• 设定区间边界：minFrame = 0，maxFrame = 30
• 给定一个二维数组（表示已占用的连续区间），例如：a = [[2,5],[10,20]]
• 需要找出[minFrame, maxFrame]范围内未被占用的缺失区间，返回结果示例：missingArray = [[0,1],[6,9],[21,30]]

实现思路 #

1. 预处理输入区间：先按区间起始值升序排序输入数组（即使输入无序也能正确处理）
2. 初始化追踪指针：从minFrame开始，作为当前待检查的起始位置
3. 遍历已占用区间：
   • 若当前追踪指针小于当前区间的起始值，说明两者之间存在缺失区间，将该区间加入结果列表
   • 更新追踪指针为当前区间的结束值+1，继续检查后续区间
4. 收尾处理：遍历完所有已占用区间后，若追踪指针仍小于等于maxFrame，则将剩余范围作为最后一个缺失区间加入结果

Python代码实现 #

def find_missing_intervals(occupied_intervals, min_frame, max_frame):
    # 按区间起始值排序，确保输入无序时也能正常计算
    sorted_intervals = sorted(occupied_intervals, key=lambda x: x[0])
    missing = []
    current_start = min_frame
    
    for start, end in sorted_intervals:
        # 跳过完全在目标范围外的区间
        if end < min_frame:
            continue
        if start > max_frame:
            break
        
        # 记录当前追踪指针到当前区间起始的缺失部分
        if current_start < start:
            missing.append([current_start, start - 1])
        
        # 更新追踪指针，确保不小于当前区间结束值+1
        current_start = max(current_start, end + 1)
        
        # 若追踪指针超出目标范围，提前终止循环
        if current_start > max_frame:
            break
    
    # 处理最后一段可能的缺失区间
    if current_start <= max_frame:
        missing.append([current_start, max_frame])
    
    return missing

# 测试示例
minFrame = 0
maxFrame = 30
a = [[2,5],[10,20]]
missingArray = find_missing_intervals(a, minFrame, maxFrame)
print(missingArray)  # 输出: [[0, 1], [6, 9], [21, 30]]

代码说明 #

• 排序逻辑：保证输入区间无序时也能按顺序检查，避免遗漏或错误计算
• 边界过滤：自动跳过完全在目标范围外的区间，增强代码通用性
• 提前终止：当追踪指针超出maxFrame时提前结束循环，提升运行效率

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