如何动态计算重叠区间离散化的插入索引，避免结果排序？

核心思路：利用输入有序特性，动态维护有序结果列表 #

输入已按lambda x: (x[0], -x[1])排序（起始点升序，同起始点则结束点降序），我们可以直接在遍历过程中维护一个始终有序、无重叠、相邻区间数据不同的结果列表，完全跳过事后排序步骤。

具体实现逻辑 #

遍历每个输入三元组(a, b, c)时，从结果列表末尾向前处理重叠/相邻情况，每个区间最多被添加、移除一次，整体时间复杂度为O(n)：

def merge_intervals(sorted_input):
    result = []
    for a, b, c in sorted_input:
        current_a, current_b, current_c = a, b, c
        right_parts = []
        
        while result:
            last_a, last_b, last_c = result[-1]
            # 当前区间完全在最后一个区间右侧，无重叠/相邻，停止处理
            if current_a > last_b + 1:
                break
            
            if current_c == last_c:
                # 数据相同，合并区间
                current_a = min(current_a, last_a)
                current_b = max(current_b, last_b)
                result.pop()
            else:
                # 数据不同，拆分重叠的旧区间
                result.pop()
                # 保留旧区间在当前区间左侧的部分
                if last_a <= current_a - 1:
                    result.append((last_a, current_a - 1, last_c))
                # 暂存旧区间在当前区间右侧的部分
                if current_b + 1 <= last_b:
                    right_parts.append((current_b + 1, last_b, last_c))
        
        # 添加处理后的当前区间
        result.append((current_a, current_b, current_c))
        # 补回旧区间的右侧部分（反转后保持顺序）
        result.extend(reversed(right_parts))
    
    return result

关键细节说明 #

1. 合并同数据区间：如果当前区间与末尾区间数据相同，无论重叠还是相邻，直接合并成更大的区间，继续向前检查是否还能合并。
2. 拆分异数据区间：如果数据不同，拆分旧区间为「当前区间左侧部分」和「当前区间右侧部分」，左侧部分保留在结果列表，右侧部分暂存后补回，确保结果无重叠且数据不重复。
3. 顺序维护：由于输入按起始点升序，所有新添加的区间（包括合并后的区间、补回的右侧部分）的起始点必然大于等于结果列表中前一个区间的结束点，因此列表始终保持有序。

性能优化建议 #

• 用原生三元组替代自定义Interval类，减少对象属性访问开销；若必须用类，添加__slots__减少内存占用：

  class Interval:
      __slots__ = ['a', 'b', 'c']
      def __init__(self, a, b, c):
          self.a = a
          self.b = b
          self.c = c
  

• 避免不必要的对象拷贝，直接操作原始数据。

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