题干与适用场景
请实现一个区间集合，支持 add([l,r))、remove([l,r))、contains(x) 和 overlaps([l,r))。插入相邻或重叠区间时要自动合并，删除可以把区间拆开；说明开闭边界、空区间和复杂度。
这道题考察有序集合、不变量和边界处理。Python bisect 文档说明二分只负责寻找插入位置，列表插入本身仍可能是 O(n)；因此候选人要说明数据规模和是否需要树结构，而不是直接声称所有操作都是 O(log n)。
面试官考察点
第一项是能否固定半开区间语义并处理相邻区间。第二项是插入和删除时只扫描可能相交的邻居，而不是每次遍历全部区间。第三项是能否根据规模选择数组、平衡树或专用区间树，并给出不变量证明。
回答前需要澄清的问题
- 区间是闭、开还是半开？ 默认使用
[l,r)，这样相邻[0,1)和[1,2)不重叠。 - 端点允许浮点数吗？ 默认是可比较的整数；浮点需要说明精度和 NaN 规则。
- 是否要求合并相邻区间？ 默认相邻也合并，以保持规范化表示。
- 数据规模和读写比例是多少？ 小规模可用有序数组，大规模考虑平衡树或区间树。
- 删除不存在的范围如何处理？ 默认幂等，不报错，只保留实际存在的部分。
30 秒回答框架
“我先固定半开区间和规范化不变量：区间按左端点排序、互不重叠且不相邻。add 用二分找到第一个可能相交的区间，向右合并重叠或相邻项；remove 找到相交区间后保留左右剩余部分。contains 看前一个区间，overlaps 用第一个右端点大于查询左端点的区间判断。数组实现搜索 O(log n) 但搬移是 O(n)；若规模大，换成平衡树或区间树。”
分步骤深入解答
第一步：定义规范化不变量
始终保存有序、互不重叠且不相邻的半开区间 [l,r)，并保证 l < r。空区间不进入集合。规范化后，任意点最多属于一个区间，插入和删除可以只围绕局部邻居操作。
第二步：选择存储结构
若区间数量不超过几千且写入不密集，有序数组简单可靠；二分搜索找到位置，插入和删除搬移数组元素。若写入和查询都很大，使用带有序键的平衡树；若需要统计覆盖数量或最大重叠深度，再考虑增强区间树。
第三步：实现插入的邻居定位
用 bisect_left 找到第一个左端点不小于 l 的位置，再检查它左侧一个区间，因为左侧区间可能延伸到 l。从这个位置向右扫描，直到下一个区间的左端点严格大于当前合并右端点；相邻区间也纳入合并。
add(l, r):
i = first index with start >= l, then i = max(0, i - 1)
while i < len(intervals) and intervals[i].end >= l:
l = min(l, intervals[i].start)
r = max(r, intervals[i].end)
delete intervals[i]
insert [l, r) at i第四步：实现删除和拆分
找到第一个可能与 [l,r) 相交的区间，逐个处理到左端点不小于 r 为止。对每个区间保留 [start,l) 和 [r,end) 中仍非空的部分。因为输入集合已经规范化，删除不会产生需要再次合并的相邻区间。
第五步：实现点查询和区间查询
contains(x) 找到最后一个 start <= x 的区间，判断 x < end。overlaps([l,r)) 找到第一个 end > l 的区间，若其 start < r 则相交；空查询区间直接返回 false。所有比较都遵循半开边界。
第六步：证明正确性
插入循环只删除与新范围重叠或相邻的区间，并把它们的并集替换为一个区间，因此不会漏掉覆盖范围。删除只移除交集并保留两侧差集。排序和不相邻不变量在每次操作后恢复，查询只需检查一个候选邻居即可。
第七步：分析复杂度
数组的二分定位是 O(log n)，但移动和合并删除可能是 O(n)，其中 n 是区间数。单次操作扫描 k 个相邻区间时还要付出 O(k)。平衡树能把定位和局部更新降到 O(log n + k)，但实现和内存开销更高。不要把二分搜索复杂度当成完整操作复杂度。
第八步：设计边界测试
测试空集合、空区间、相邻合并、完全包含、部分重叠、跨越多个区间、删除中间部分、删除端点、负数、重复操作和大范围查询。随机生成操作，与逐点布尔数组模型对拍，验证集合的覆盖结果一致。
设计取舍与边界
取舍一：半开还是闭区间
半开区间让相邻范围自然拼接，长度是 r-l，适合时间和数组下标。若业务使用闭区间，必须把相邻判定、长度和整数溢出规则统一改变，不能只改比较符号。
取舍二：数组还是平衡树
数组代码短、缓存友好，适合读多写少和中小规模。平衡树适合大量插入删除，但需要稳定的有序键和迭代器失效规则。先用实际 n、写入比例和延迟预算做选择。
取舍三：是否合并相邻范围
合并相邻范围能减少条目数量并简化查询；若业务必须保留原始段边界，就应存储来源元数据，不能只用一个并集区间替换历史。
失败演练与演进计划
演练一：大量相邻插入
按相反顺序插入 10,000 个相邻区间，验证最终只剩一个规范化区间，且没有遗漏端点。观察数组搬移成本，判断是否需要树结构。
演练二：随机插入和删除
随机生成 add/remove/contains/overlaps，与逐点模型对拍。重点检查删除把一个区间拆成两段后，后续插入能正确合并。
演练三：边界和异常输入
测试 l == r、l > r、极大整数和 NaN。明确空区间返回、反向区间报错或交换，以及浮点输入是否被拒绝。
常见误区与追问
误区一：把相邻和重叠混为一谈
半开 [0,1) 与 [1,2) 没有交集，但题目若要求规范化相邻区间仍可合并。要分别定义交集和合并条件。
误区二：只检查右侧邻居
左侧区间可能跨过新范围左端点。二分后必须回看一个前驱。
误区三：删除后留下空区间
保留左右差集时过滤 start >= end 的结果，否则 contains 会出现幽灵命中。
误区四：声称 bisect 让插入 O(log n)
Python 文档明确指出列表插入搬移是 O(n)。应完整说明搜索、搬移和扫描成本。
误区五：忽略浮点边界
NaN 不满足正常排序关系，近似相等也会让相邻判断不稳定。若业务允许浮点，先定义规范化精度。
误区六：没有保留来源信息
如果区间代表权限、预订或账期，简单合并可能丢失来源。此时需要额外元数据或选择不合并的表示。