区间类问题有哪些通用解题套路？（排序 + 扫描）

简化版

区间问题（合并、重叠、覆盖、选择等）几乎都遵循同一个套路：先排序，再线性扫描。关键是按哪个端点排序——求「合并/统计重叠」通常按左端点排序，求「最多不重叠/最少箭」通常按右端点排序。排序后用一个「当前区间的边界」变量边扫边判断两区间是否重叠（当前.start <= 上一个.end 即重叠），据此合并或计数。另有一类用**扫描线（差分/事件排序）**统计任意时刻的重叠数。

详细版

判断两区间 [a1,b1] 和 [a2,b2] 是否重叠（假设 a1 <= a2）：a2 <= b1 即重叠（后一个的起点没超过前一个的终点）。

三大套路：

套路	按什么排序	典型题
合并/统计重叠	左端点升序	合并区间 56、插入区间 57、会议室 II 253
贪心选最多不重叠 / 最少点	右端点升序	无重叠区间 435、用最少箭引爆气球 452
扫描线（差分事件）	把端点拆成 +1/-1 事件排序	会议室 II、天际线、区间重叠计数

通用代码骨架（合并类）：

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);   // 按左端点排序
List<int[]> res = new ArrayList<>();
for (int[] cur : intervals) {
    if (res.isEmpty() || res.get(res.size()-1)[1] < cur[0]) {
        res.add(cur);                             // 不重叠，新开一段
    } else {
        res.get(res.size()-1)[1] =                // 重叠，合并右端点取 max
            Math.max(res.get(res.size()-1)[1], cur[1]);
    }
}

完整版教学

一、为什么区间问题几乎都要先排序

区间在原始输入里是乱序的，两两之间的重叠关系需要 O(n²) 才能全部判断。排序把区间按某个端点排成有序序列后，重叠关系就变成「只需和相邻/前一个区间比较」的局部关系，从而一次线性扫描就能处理。所以「排序 + 扫描」是区间问题的万能开场。真正的技巧在于——排序的关键字（左端点还是右端点）取决于你要求什么。

二、什么时候按左端点排

当你要「合并重叠区间」或「统计某处堆叠了几个区间」时，按左端点升序排。

道理：按左端点排序后，区间是「从左往右依次进场」的。你维护一个「当前合并段的右边界 end」，新区间的左端点若 <= end，就和当前段重叠 → 合并（end = max(end, 新区间右端)）；若 > end，就与当前段脱离 → 收尾旧段、新开一段。左端点有序保证了「一旦脱离就永久脱离」，不会有更左的区间在后面冒出来打乱。

典型：合并区间 56、插入区间 57。

三、什么时候按右端点排

当你要「选出最多互不重叠的区间」或「用最少的点/箭覆盖所有区间」时，按右端点升序排（贪心）。

道理：要塞进尽可能多的不重叠区间，就该每次选「结束最早」的那个——它右端点小，给后面留的空间最大。所以按右端点排序，贪心地依次挑「与已选区间不冲突」的区间。无重叠区间 435（求最少删除数 = 总数 − 最多不重叠数）、用最少箭引爆气球 452 都是这个模型。

口诀：合并看左端点，贪心选择看右端点。

四、扫描线（差分/事件）套路

第三类问题问「任意时刻最多有几个区间同时存在」（如会议室 II 求最少会议室、天际线问题）。这类适合扫描线：

把每个区间 [start, end] 拆成两个事件：start 处 +1（进来一个），end 处 -1（走了一个）。
把所有事件按时间排序，从左扫到右，维护一个计数器，计数器的峰值就是最大重叠数。
边界处理：同一时刻先处理 -1（结束）还是 +1（开始）取决于区间是否算「端点接触」重叠，要按题意定。

这等价于差分数组思想在区间端点上的应用。

五、判断重叠的通用条件（别记反）

两区间 A=[a1,b1]、B=[a2,b2]：

重叠的充要条件：a1 <= b2 && a2 <= b1（各自起点都不超过对方终点）。
若已按左端点排序保证 a1 <= a2，则简化为 a2 <= b1（后者起点落在前者内）。
不重叠：b1 < a2（前者完全在后者左边）。

注意「端点相接算不算重叠」（如 [1,2] 和 [2,3]）要看题目定义，用 < 还是 <= 由此决定，这是最常见的边界坑。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：排序把二维的起止关系变成可单向扫描的序列；按左端适合合并/覆盖，按右端适合选择最多不重叠。

区间 `[a,b]` 与 `[c,d]` 相交条件为 `max(a,c)≤min(b,d)`；左闭右开则端点相等不重叠

数字推演：会议 [1,3) 与 [3,5) 可复用房间，而闭区间气球 [1,3]、[3,5] 可被 x=3 一箭命中。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：必须先明确开闭端点、是否已排序、静态还是动态；扫描线同坐标事件顺序由端点语义决定。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：排序把二维的起止关系变成可单向扫描的序列；按左端适合合并/覆盖，按右端适合选择最多不重叠。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“会议 [1,3) 与 [3,5) 可复用房间，而闭区间气球 [1,3]、[3,5] 可被 x=3 一箭命中”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：必须先明确开闭端点、是否已排序、静态还是动态；扫描线同坐标事件顺序由端点语义决定。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：区间题一律按左端排序。 选择最多不重叠通常按右端排序。
误区：端点相等总算重叠。 取决于闭区间还是半开区间。
误区：扫描线同坐标事件顺序无关。 开始/结束先后会改变重叠计数。
追问：怎样选排序键？ 看扫描中要固定的是最早开始、最早结束还是覆盖范围。
追问：什么时候用堆？ 动态维护当前最早结束或并发资源数时。
追问：动态预约为何不能每次全排序？ 应使用有序树等结构找相邻区间。

九、加强记忆

区间问题万能套路 = 排序 + 线性扫描，胜负手在排序关键字：合并/统计重叠按左端点升序（维护当前段右界 end，新区间左端 ≤ end 就合并）；贪心选最多不重叠/最少箭按右端点升序（每次选结束最早的，留最大空间）；求任意时刻最大重叠用扫描线（端点拆成 +1/-1 事件排序，计数峰值即答案）。判重叠记 a2 <= b1（左端已排序时），端点相接算不算重叠决定用 < 还是 <=。一句话：合并看左、贪心看右、堆叠用扫描线。

简化版

详细版