求助实现SplitMerge函数合并regular_events与special_events

问题定义 #

给定两个已按开始时间排序、内部无重叠的事件区间数组：

• regular_events：常规事件数组，元素格式为[start_time, end_time]
• special_events：特殊事件数组，元素格式为[start_time, end_time]

需实现SplitMerge函数，按以下规则合并：

• 无重叠的事件直接加入结果
• 若常规事件与特殊事件重叠，保留特殊事件，拆分/调整常规事件（移除重叠部分）
• 特殊事件、常规事件各自内部无重叠
• 两个数组均已按开始时间排序

现有代码的问题 #

GitHub Copilot提供的代码存在逻辑缺陷：当常规事件被特殊事件切割后，剩余的常规区间会直接被加入结果，不再与后续的特殊事件比对，无法处理一个常规事件与多个特殊事件重叠的场景（如跨重叠案例）。

四类测试场景 #

1. 无重叠场景 #

输入：

regular_events = [[5, 10]]
special_events = [[0, 3], [12, 15]]

预期输出：
[[0, 3], [5, 10], [12, 15]]

2. 部分重叠场景 #

输入：

regular_events = [[4, 10]]
special_events = [[6, 8]]

预期输出：
[[4, 6], [6, 8], [8, 10]]

3. 完全重叠场景 #

输入：

regular_events = [[5, 10]]
special_events = [[3, 12]]

预期输出：
[[3, 12]]

4. 跨重叠场景 #

输入：

regular_events = [[2, 12]]
special_events = [[3, 5], [7, 9], [10, 11]]

预期输出：
[[2, 3], [3, 5], [5, 7], [7, 9], [9, 10], [10, 11], [11, 12]]

正确实现方案 #

核心思路：当常规事件与特殊事件重叠并被切割后，剩余的常规区间需要继续参与循环，与后续的特殊事件比对，而非直接跳过。

def SplitMerge(regular_events, special_events):
    merged = []
    i = j = 0
    n, m = len(regular_events), len(special_events)
    
    while i < n and j < m:
        reg_start, reg_end = regular_events[i]
        spe_start, spe_end = special_events[j]
        
        # 常规事件在特殊事件之前，无重叠
        if reg_end <= spe_start:
            merged.append(regular_events[i])
            i += 1
        # 特殊事件在常规事件之前，无重叠
        elif spe_end <= reg_start:
            merged.append(special_events[j])
            j += 1
        # 存在重叠，处理切割逻辑
        else:
            # 常规事件开头有不重叠部分，加入结果
            if reg_start < spe_start:
                merged.append([reg_start, spe_start])
            # 加入特殊事件
            merged.append(special_events[j])
            # 更新常规事件的剩余部分：如果常规事件结束在特殊事件之后，保留剩余区间继续处理
            if reg_end > spe_end:
                regular_events[i] = [spe_end, reg_end]
            else:
                # 常规事件完全被覆盖，移动常规事件指针
                i += 1
            # 移动特殊事件指针
            j += 1
    
    # 处理剩余的常规事件
    while i < n:
        merged.append(regular_events[i])
        i += 1
    # 处理剩余的特殊事件
    while j < m:
        merged.append(special_events[j])
        j += 1
    
    return merged

测试验证 #

针对四类场景分别测试，均能得到预期输出：

1. 无重叠场景：返回[[0, 3], [5, 10], [12, 15]]
2. 部分重叠场景：返回[[4, 6], [6, 8], [8, 10]]
3. 完全重叠场景：返回[[3, 12]]
4. 跨重叠场景：返回[[2, 3], [3, 5], [5, 7], [7, 9], [9, 10], [10, 11], [11, 12]]

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