本文介绍一种基于非重叠区间树的高效方法，用于从形如 [lower, upper, data...] 的嵌套列表中筛选出互不重叠的区间，避免暴力遍历导致的逻辑错误与性能问题。
本文介绍一种基于非重叠区间树的高效方法，用于从形如 `[lower, upper, data...]` 的嵌套列表中筛选出互不重叠的区间，避免暴力遍历导致的逻辑错误与性能问题。
在处理区间数据（如时间片段、坐标范围或资源分配段）时，常需剔除相互重叠的条目，仅保留彼此分离的“干净”区间。原始代码试图通过双重循环和原地 remove() 操作实现，但存在严重缺陷：边遍历边修改列表会跳过元素、引发索引错乱，且重叠判定逻辑不完整（未覆盖包含、相切等边界情况）；此外，时间复杂度高达 O(n²)，难以扩展。
更优解是构建 非重叠区间树（Non-Overlapping Interval Tree） —— 一种定制化二叉搜索树结构：
- 根节点存储一个合法区间；
- 左子树仅容纳完全位于当前区间左侧（即
upper ≤ current.lower）的区间； - 右子树仅容纳完全位于当前区间右侧（即
lower ≥ current.upper）的区间； - 若新区间与当前节点重叠（即
not (upper ≤ current.lower or lower ≥ current.upper)），则拒绝插入并抛出异常。
该设计确保树中所有区间天然互不重叠，且平均插入/查询复杂度为 O(log n)，整体构建效率达 O(n log n)。
以下是完整可运行实现：
huaweicloud-python-sdk-helper
下载
华为云 Python SDK 查询工具。自动发现已安装 SDK 的服务包、Client类、API 方法、入参详情、类信息（__init__ 参数、属性、类型、描述），支持关键字搜索，快速定位目标 API 使用方法。
立即学习“Python免费学习笔记（深入）”；
class Interval:
def __init__(self, lower_bound, upper_bound):
self.lower_bound = lower_bound
self.upper_bound = upper_bound
class NonOverlappingIntervalTree:
def __init__(self):
self.interval = None
self.left = None
self.right = None
def add_interval(self, lower_bound, upper_bound):
if not self.interval:
self.interval = Interval(lower_bound, upper_bound)
return
# 若新区间完全在左：upper ≤ 当前下界
if upper_bound <= self.interval.lower_bound:
if self.left is None:
self.left = NonOverlappingIntervalTree()
self.left.add_interval(lower_bound, upper_bound)
# 若新区间完全在右：lower ≥ 当前上界
elif lower_bound >= self.interval.upper_bound:
if self.right is None:
self.right = NonOverlappingIntervalTree()
self.right.add_interval(lower_bound, upper_bound)
# 否则重叠 → 拒绝插入
else:
raise ValueError("Interval overlaps with existing interval")
def cut_overlapping_ranges(ranges):
"""
过滤掉重叠区间，保留首个遇到的非重叠版本。
Args:
ranges: List[List[int, int, ...]], 每个子列表至少含 [lower, upper]
Returns:
List[List]: 无重叠的原始列表（保持输入顺序中首次出现的有效项）
"""
output = []
tree = NonOverlappingIntervalTree()
for item in ranges:
lower, upper, *data = item
try:
tree.add_interval(lower, upper)
output.append(item) # 仅当成功插入才保留原始项（含 data）
except ValueError:
continue
return output✅ 使用示例：
input_ranges = [[0, 10, 'A'], [5, 15, 'B'], [11, 18, 'C'], [10, 25, 'D'], [20, 25, 'E'], [30, 35, 'F']] result = cut_overlapping_ranges(input_ranges) print(result) # 输出: [[0, 10, 'A'], [11, 18, 'C'], [20, 25, 'E'], [30, 35, 'F']]
⚠️ 注意事项：
- 本方案按输入顺序依次尝试插入，因此保留的是每个不重叠位置上“最先出现”的区间；若需保留最长、权重最高或其它策略的区间，需预排序后再处理；
- 区间判定采用半开区间逻辑（
[a, b)风格隐含），即[10, 25]与[11, 18]视为重叠（因 11 ∈ (10,25)），而[0,10]与[10,25]默认不重叠（右端点相接不视为重叠）；如需包含相接情况，将判定条件改为upper_bound 和 <code>lower_bound > self.interval.upper_bound； - 实际生产环境可考虑使用成熟库（如
intervaltree或sortedcontainers），但理解此手写结构对掌握区间算法原理至关重要。
该方法兼顾正确性、可读性与扩展性，是处理大规模区间去重任务的专业级实践方案。
