如何优化重叠区间拆分算法、适配通用场景并修复实现问题？

我编写了一个Python脚本，用于将重叠区间拆分为唯一区间，迭代版本已完成多轮迭代。当前版本输出正确，且性能优于某Stack Overflow答案中的实现，已通过暴力法及逻辑验证确认输出准确性。

问题背景 #

假设有一排无限编号的盒子，每个盒子只能存放最后放入的对象，初始状态为空。输入是三元组列表，每个三元组的前两个元素为整数区间的起止值（起始≤结束），第三个元素是要放入盒子的内容。例如(0, 10, 'A')表示把'A'放入0到10号盒子（包含两端）。我们需要用最少的三元组描述执行所有指令后的盒子状态，场景分为两种：

• 窄场景：任意两个三元组(s1, e1, d1)、(s2, e2, d2)都不满足s1 < s2 < e1 < e2，包含4个子场景及额外规则；
• 通用场景：存在区间交叉情况，遵循“起始较晚者优先”的规则。

现有实现 #

1. 暴力法实现 #

输出正确但性能较慢，可处理通用场景，代码如下：

def brute_force_discretize(ranges):
    numbers = {}
    ranges.sort(key=lambda x: (x[0], -x[1]))
    for start, end, data in ranges:
        numbers |= {n: data for n in range(start, end + 1)}
    numbers = list(numbers.items())
    l = len(numbers)
    i = 0
    output = []
    while i < l:
        di = 0
        curn, curv = numbers[i]
        while i < l and curn + di == numbers[i][0] and curv == numbers[i][1]:
            i += 1
            di += 1
        output.append((curn, numbers[i-1][0], curv))
    return output

2. 高效实现（仅支持窄场景） #

性能优异但只能处理窄场景，且未利用输入已按升序排序的特性做优化，代码如下：

from typing import Any, List, Tuple


def get_nodes(ranges: List[Tuple[int, int, Any]]) -> List[Tuple[int, int, Any]]:
    nodes = []
    for ini, fin, data in ranges:
        nodes.extend([(ini, False, data), (fin, True, data)])
    return sorted(nodes)


def merge_ranges(data: List[List[int | Any]], range: List[int | Any]) -> None:
    if not data or range[2] != (last := data[-1])[2] or range[0] > last[1] + 1:
        data.append(range)
    else:
        last[1] = range[1]


def discretize_narrow(ranges):
    nodes = get_nodes(ranges)
    output = []
    stack = []
    actions = []
    for node, end, data in nodes:
        if not end:
            action = False
            if not stack or data != stack[-1]:
                if stack and start < node:
                    merge_ranges(output, [start, node - 1, stack[-1]])
                stack.append(data)
                start = node
                action = True
            actions.append(action)
        elif actions.pop(-1):
            if start <= node:
                merge_ranges(output, [start, node, stack.pop(-1)])
                start = node + 1
            else:
                stack.pop(-1)
    return output

当前待解决问题 #

• 输入已按升序排序，但现有高效实现未利用该特性，如何优化以提升性能？
• 如何修改现有实现，使其支持通用区间交叉场景？
• 某已被接受的算法（discretize_gen）在窄场景下存在错误，例如无法正确处理部分区间覆盖情况，如何修复该算法？

此外，部分现有实现存在边缘案例错误，比如区间结果截断、合并错误等，需要同步解决这些问题。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος