求高效分离排序带标签重叠区间的初等区间提取算法

核心思路 #

要实现带标签的重叠区间拆分，关键是先提取所有区间的端点并排序去重，再逐个遍历相邻端点构成的子区间，收集所有覆盖该子区间的原区间标签，最终生成标签合并后的新区间列表。该方法的时间复杂度由排序操作主导，为O(n log n)，属于高效实现。

实现代码 #

from typing import List, Set

class Interval:
    def __init__(self, a: float, b: float, labels: Set[str]):
        self.a = a
        self.b = b
        self.labels = labels

    def __eq__(self, other):
        # 重写相等判断方法，用于结果验证
        if not isinstance(other, Interval):
            return False
        return (self.a == other.a and 
                self.b == other.b and 
                self.labels == other.labels)

    def __repr__(self):
        # 自定义打印格式，方便调试查看
        return f"Interval({self.a}, {self.b}, {self.labels})"


def separateIntervals(intervals: List[Interval]) -> List[Interval]:
    if not intervals:
        return []
    
    # 提取所有区间的端点，去重后排序
    points = sorted({point for interval in intervals for point in (interval.a, interval.b)})
    result = []

    # 遍历每一对相邻端点，生成子区间
    for i in range(len(points) - 1):
        start = points[i]
        end = points[i+1]
        if start >= end:
            continue
        
        # 收集所有覆盖当前子区间的标签集合
        current_labels = set()
        for interval in intervals:
            if interval.a <= start and interval.b >= end:
                current_labels.update(interval.labels)
        
        if current_labels:  # 仅保留有标签关联的子区间
            result.append(Interval(start, end, current_labels))
    
    return result

示例验证 #

# 测试给定的示例场景
intervalA = Interval(0, 3, {"foo"})
intervalB = Interval(2, 4, {"bar"})
intervals = [intervalA, intervalB]

actualOutput = separateIntervals(intervals)
desiredOutput = [
    Interval(0, 2, {"foo"}),
    Interval(2, 3, {"foo", "bar"}),
    Interval(3, 4, {"bar"})
]

print(actualOutput == desiredOutput)  # 输出 True

关键说明 #

1. 端点处理：通过集合去重避免重复端点，排序后得到所有拆分的关键节点，确保子区间的划分精准。
2. 标签合并：对每个子区间，检查所有原区间是否覆盖它（因子区间由原区间端点拆分而来，只需判断原区间左端点≤子区间起点、右端点≥子区间终点即可），合并所有符合条件的标签。
3. 相等判断：重写__eq__方法是为了直接对比两个Interval对象的所有属性，方便验证结果是否符合预期。

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