本文介绍一种专为小规模（通常1–3个）非重叠、非相邻区间设计的高性能 Difference 算法，可在不排序、低内存分配前提下，快速计算新区间与现有区间集合的相对补集（即“新区间中未被覆盖的部分”）。
本文介绍一种专为小规模（通常1–3个）非重叠、非相邻区间设计的高性能 `difference` 算法，可在不排序、低内存分配前提下，快速计算新区间与现有区间集合的相对补集（即“新区间中未被覆盖的部分”）。
在处理动态区间合并与排除场景（如内存分配追踪、日志范围过滤、时间窗口剔除等）时，常需频繁执行「给定新区间，求其与当前已知不重叠区间集合的差集」操作。问题关键在于：集合规模极小（95% 为 1 或 2 个区间），但调用频次高；排序开销成为瓶颈，需避免 sort.Sort 的 O(n log n) 成本。
针对该约束，peterSO 提出的 Difference 实现是目前最优解：它采用原地选择性最小化排序 + 单次线性扫描策略，在保持代码简洁的同时，将平均耗时降低近 40%，内存分配减少 25%。
核心思路
不预先对整个区间集合排序，而是在遍历过程中，每次仅将当前待处理的最小起始点区间“冒泡”至切片头部（通过一次内层循环完成局部最小值提取）。随后，用该区间与目标区间 b 逐段裁剪：
- 若
b完全位于当前区间左侧 → 整个b加入结果； - 若
b起始点在当前区间左侧 → 截取[b.Start, a[0].Start−1]，并推进b.Start； - 若
b结束点在当前区间内或右侧 → 推进b.Start至a[0].End + 1； - 处理完所有区间后，剩余
b（若有效）直接追加。
该逻辑天然适配小规模数据：最坏情况（3 个区间）仅需最多 3 次局部查找 + 3 次比较，无递归、无额外切片扩容（预估容量为 3），零指针间接访问。
示例代码（Go 实现）
func (a Intervals) Difference(b Interval) Intervals {
if len(a) == 0 {
return Intervals{b}
}
var d Intervals // 预分配容量可设为 3，因最多产生 len(a)+1 段
for len(a) > 0 {
// ⚡ 局部最小化：将起始点最小的区间移到 a[0]
for i := 1; i <h3>注意事项与最佳实践</h3>
-
输入假设必须满足：
a中的区间必须是非重叠（non-overlapping）且非相邻（non-adjacent），否则裁剪边界可能出错（相邻区间如{10,15}和{16,20}应被合并为{10,20}后再参与差集计算）； -
性能敏感点：该算法优势在
len(a) ≤ 3时最大化；若集合规模增长（如 > 10），应切换为先排序 + 双指针扫描方案； -
内存友好性：返回切片
d使用var d Intervals声明，避免make(Intervals, 0, 3)的显式初始化（Go 编译器对零值切片追加有优化）； -
边界安全：所有区间端点比较均使用
≤/显式判断，杜绝整数溢出或空区间误判（如Start > End时自动跳过）。
综上，此方案以极简逻辑、零依赖、亚百纳秒级延迟，完美匹配高频、小规模区间差集场景，是生产环境区间运算库的推荐实现范式。
