区间交集算法（多区间交集）
字数 1117 2025-10-26 19:15:23
区间交集算法（多区间交集）
题目描述：给定多个区间列表，每个列表包含若干个已排序且不重叠的闭区间。要求找出所有区间列表中共同的交集区间。例如，输入为[[1, 3], [5, 9]]、[[2, 4], [6, 8]]和[[3, 7]]，则交集区间为[3, 4]和[6, 7]。
解题过程：
-
问题分析：
- 每个区间列表已按起始点排序且内部无重叠。
- 目标是找到所有列表中都存在的区间部分。
- 核心思路是逐步比较区间，利用区间重叠的性质缩小范围。
-
关键思路：
- 交集区间的起始点取所有当前区间起始点的最大值（保证在所有区间内）。
- 交集区间的结束点取所有当前区间结束点的最小值（保证不超出任何区间）。
- 若起始点小于等于结束点，则形成一个有效交集区间。
-
逐步求解：
- 步骤1：初始化指针数组，每个指针指向各列表的第一个区间。
- 步骤2：循环直到任一列表的区间被遍历完：
a. 找出所有指针指向区间的最大起始点（max_start）和最小结束点（min_end）。
b. 若max_start ≤ min_end，说明存在交集[max_start, min_end]，将其加入结果。
c. 将指向结束点最小的区间的指针后移（因为该区间无法再与其他区间产生更长的交集）。 - 步骤3：输出所有找到的交集区间。
-
示例演算（输入：[[1,3],[5,9]]、[[2,4],[6,8]]、[[3,7]]）：
- 初始指针指向[1,3]、[2,4]、[3,7]：
- max_start = max(1,2,3) = 3, min_end = min(3,4,7) = 3 → 交集[3,3]（即[3,3]）。
- 最小结束点3来自第一个列表，指针后移至[5,9]。
- 当前区间：[5,9]、[2,4]、[3,7]：
- max_start = max(5,2,3) = 5, min_end = min(9,4,7) = 4 → 5>4，无交集。
- 最小结束点4来自第二个列表，指针后移至[6,8]。
- 当前区间：[5,9]、[6,8]、[3,7]：
- max_start = max(5,6,3) = 6, min_end = min(9,8,7) = 7 → 交集[6,7]。
- 最小结束点7来自第三个列表，列表遍历完毕。
- 结果：[3,3]和[6,7]（实际可合并处理，但本题要求多区间交集，保留离散结果）。
- 初始指针指向[1,3]、[2,4]、[3,7]：
-
复杂度分析：
- 时间复杂度：O(N*K)，N为列表数量，K为最长列表的区间数（每个区间被处理一次）。
- 空间复杂度：O(K)存储结果（最坏情况交集数与最长列表相同）。