题目重点：从数组删除索引扩展到有序结构，使用前驱/后继检查新段不重叠并分析数组与平衡树成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版区间为整数半开 [start,end)，start<end；相邻 [1,3) 与 [3,5) 允许共存且不自动合并。初始列表按 start 升序且不重叠。
- 静态问题按 0-based 索引删除并返回新列表；动态 remove 按完整 (start,end) 精确匹配。题目未固定这些接口/端点规则。
解题路线
- 静态只删一次：可返回 intervals[:i]+intervals[i+1:]，时间 O(N) 因为要复制剩余输出；若允许原地且不保序，末尾交换可 O(1)，但题意是区间数组且很可能要求顺序，不能擅自改变。
- 频繁删除又要保持有序时，数组中间删除搬移 O(N)；用平衡有序树以 start 为键，删除已知 key O(log N)，若按索引删除还需 order-statistics 子树大小，普通 BST 不支持 O(log N) 第 i 项。
- 动态插入 [a,b) 时找 start≥a 的后继和前驱，检查前驱.end≤a 且 b≤后继.start；满足才插入，否则拒绝。只检查相邻两段充分，因为现有区间两两不重叠且按 start 排序。
- 若规范要求自动合并相邻/重叠区间，需改为寻找所有重叠段并删除合并，复杂度带被合并数 K；该题目仅说保持不相交，没有说 union 语义。
- 示例代码用 Python sorted list 与 bisect 便于核正确性，二分找位置 O(log N) 但 insert/pop 搬移 O(N)；生产需要平衡树/跳表才能得到 O(log N) 更新。
手动走一遍
当前 [1,3),[5,7)。插 [3,5) 与两邻相接但不重叠，可得三段；插 [2,6) 会碰两邻，必须拒绝。按索引 1 删 [5,7) 后只剩 [1,3)。若改闭区间，相接端点判断需改。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training contract: half-open [start,end) integer intervals, non-overlapping.
Static delete_by_index returns a new list. Dynamic add/remove use a sorted
array for clarity; Python list shifts are O(N). A balanced ordered tree would
make predecessor/successor search plus updates O(log N).
"""
from bisect import bisect_left
def delete_by_index(intervals: list[tuple[int, int]], index: int) -> list[tuple[int, int]]:
if not 0 <= index < len(intervals):
raise IndexError(index)
return intervals[:index] + intervals[index + 1:]
class DisjointIntervals:
def __init__(self):
self.items: list[tuple[int, int]] = []
def add(self, start: int, end: int) -> bool:
if start >= end:
raise ValueError('empty or reversed interval')
pos = bisect_left(self.items, (start, end))
if pos > 0 and self.items[pos - 1][1] > start:
return False
if pos < len(self.items) and end > self.items[pos][0]:
return False
self.items.insert(pos, (start, end))
return True
def remove(self, start: int, end: int) -> bool:
pos = bisect_left(self.items, (start, end))
if pos == len(self.items) or self.items[pos] != (start, end):
return False
self.items.pop(pos)
return True
复杂度
静态返回新数组 O(N) 时间/空间。示例动态列表 add/remove 找位置 O(log N)、搬移 O(N)、存储 O(N)；有序平衡树按 start 的 add/remove O(log N) 时间、O(N) 空间，按 rank 删除需扩展 order-statistics。
易错点与追问
容易失分的边界
- 只二分查找就声称 Python list 插删 O(log N)。
- 未说区间端点开闭导致相接判断错。
- 插新段只检查一个邻居。
- 按索引删除与按区间 key 删除混同。
- 未定义重叠时是拒绝、覆盖还是合并。
继续深挖
- 按索引频繁删除怎样在 O(log N) 找到第 i 项？
- 如果支持区间合并，算法怎样变？
- 若两个区间在端点相接，闭区间与半开区间结论有何不同？
- 多线程同时插入相交段怎样保证不变量？
