区间重叠

概述

区间重叠（Interval Overlap）是判断两个闭区间是否有交集的操作。它是 区间树 支持的核心查询原语，也是计算几何、日程调度、资源分配等领域的基本操作。两个闭区间 $[a,b]$ 和 $[c,d]$ 重叠的判定条件为 $a\le d$ 且 $c\le b$，即一个区间的起点不超过另一个区间的终点。

定义

区间重叠

给定两个闭区间 $i_1=[a,b]$ 和 $i_2=[c,d]$（其中 $a\le b$，$c\le d$），称 $i_1$ 与 $i_2$ 重叠（overlap），当且仅当： $a\le d\text{且}c\le b$

等价地，$i_1$ 与 $i_2$ 不重叠（即完全分离），当且仅当： $b<c\text{或}d<a$

即一个区间的终点严格小于另一个区间的起点。

判定的直观理解

两个区间重叠，意味着它们在数轴上有公共部分。两个区间不重叠，意味着一个区间完全在另一个区间的左边或右边。

不重叠的情况：          重叠的情况：

[a, b]    [c, d]       [a, b]
  ↑        ↑             ↑
  b < c               [c, d]
  (i1 在 i2 左边)        ↑
                     a ≤ d 且 c ≤ b
                     (有公共部分 [c, b])

生活化类比

想象两条时间线上的会议安排：

• 会议 A：上午 9:00 - 10:30
• 会议 B：上午 10:00 - 11:30

A 的结束时间（10:30）> B 的开始时间（10:00），且 B 的结束时间（11:30）> A 的开始时间（9:00），所以两个会议在时间上有重叠（10:00 - 10:30）。

再看：

• 会议 C：上午 9:00 - 10:00
• 会议 D：上午 10:30 - 11:30

C 的结束时间（10:00）< D 的开始时间（10:30），所以两个会议不重叠，中间有 30 分钟的空闲。

核心性质

性质1：判定条件的对称性

区间重叠的判定条件关于两个区间是对称的：

$a\le d\text{ 且 }c\le b⟺c\le b\text{ 且 }a\le d$

这意味着无论先检查哪个区间，结果相同。

性质2：不重叠条件的互斥性

两个区间不重叠有两种互斥的情况：

• $i_1$ 完全在 $i_2$ 左边：$b<c$
• $i_1$ 完全在 $i_2$ 右边：$d<a$

这两种情况不可能同时成立（因为 $a\le b$ 且 $c\le d$）。

性质3：重叠的传递性不成立

区间重叠不满足传递性。即：如果 $i_1$ 与 $i_2$ 重叠，$i_2$ 与 $i_3$ 重叠，$i_1$ 与 $i_3$ 不一定重叠。

反例：$i_1=[1,3]$，$i_2=[2,5]$，$i_3=[4,6]$

• $i_1$ 与 $i_2$ 重叠（公共部分 $[2,3]$）
• $i_2$ 与 $i_3$ 重叠（公共部分 $[4,5]$）
• $i_1$ 与 $i_3$ 不重叠（$3<4$）

性质4：端点接触算重叠

根据闭区间的定义，$[a,b]$ 与 $[b,c]$ 是重叠的（公共点为 $b$）。这是因为 $a\le c$（由 $a\le b\le c$）且 $b\le b$，两个条件均满足。

如果使用开区间 $(a,b)$ 和 $(c,d)$，则 $(a,b)$ 与 $(b,c)$ 不重叠。区间树中通常使用闭区间。

性质5：区间树利用端点排序加速重叠检测

在 区间树 中，节点按区间的低端点 low 排序（红黑树的中序遍历按 low 递增）。查询时，利用 max 属性（子树中所有区间的最大高端点）进行剪枝：

• 如果 $x.\text{left}.\text{max}<i.\text{low}$，则左子树中所有区间的 $\text{high}$ 都 $<i.\text{low}$，由不重叠条件 $b<c$ 可知，左子树中没有任何区间与 $i$ 重叠，可以安全剪枝。

这一剪枝策略将查询的期望时间从 $O(n)$ 降低到 $O(\lg n)$。

重叠的伪代码

INTERVAL-OVERLAP(i1, i2)
1  if i1.high >= i2.low and i2.high >= i1.low
2      return true
3  else
4      return false

等价的否定形式（不重叠判定）：

INTERVAL-NO-OVERLAP(i1, i2)
1  if i1.high < i2.low or i2.high < i1.low
2      return true
3  else
4      return false

重叠的类型

两个区间重叠时，根据重叠的程度，可以分为以下几种类型：

类型	条件	示例	图示
包含	一个区间完全包含另一个	$[1,10]$ 与 $[3,7]$	[===]
部分重叠	两个区间有公共部分但互不包含	$[1,5]$ 与 $[3,8]$	[==]===]
端点接触	仅共享一个端点	$[1,5]$ 与 $[5,9]$	`[==]
完全相同	两个区间完全一样	$[1,5]$ 与 $[1,5]$	[====]

应用场景

区间重叠判定在许多实际问题中有广泛应用：

应用领域	具体问题	区间含义
日程管理	检查会议时间冲突	会议的开始和结束时间
资源分配	检查资源占用冲突	资源被占用的起止时间
基因组学	寻找基因片段重叠	DNA 片段在染色体上的位置
数据库	时间范围查询	事件的发生时间范围
网络	端口/地址范围冲突	网络地址的分配范围
版本控制	代码变更冲突检测	代码行号的范围

参见

• 区间树 — 利用区间重叠判定实现高效区间查询的数据结构
• 数据结构扩张 — 区间树是数据结构扩张的典型案例
• 数据结构扩张四步法 — 系统化推导区间树的四步方法论
• 红黑树扩张定理 — 区间树中 max 属性维护的理论基础