【Hot100】区间问题

这一类的核心思想是：通过排序将无序的区间转化为有序序列，从而将复杂的“全局比较”简化为线性的“相邻比较”。

• 解题套路：
  1. 排序 (Sort)：
     • 通常按 左端点 (start) 升序排序（用于合并、插入）。
     • 有时按 右端点 (end) 升序排序（用于贪心选点，如射气球）。
  2. 线性扫描 (Linear Scan)：
     • 维护一个“当前合并后的区间”或“当前覆盖范围”。
     • 遍历后续区间，判断是否与当前区间 重叠。
     • 重叠：更新边界（通常是 max(end)）。
     • 不重叠：将当前区间加入结果集，并开始处理新的区间。
• 重叠判断：
  • 若已排序（按左端点）：区间 A [a1, a2] 和 B [b1, b2] (其中 a1 <= b1)。
  • 重叠条件：a2 >= b1。
  • 合并后：[a1, max(a2, b2)]。

📝 本类题型总结

题目	核心技巧	关键差异点 (vs 合并区间)
56. 合并区间	左端点排序 + 合并	基准：按 start 排序。重叠则 end = max(end)。
57. 插入区间	分段处理	利用原有序性。分 左不重叠、中重叠合并、右不重叠 三段。
452. 射气球	右端点排序 + 贪心	按 end 排序。找 最少点。若 start > pos 则换新箭。

---

🏆 母题：LeetCode 56. 合并区间 (Merge Intervals)

题目内容：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
核心逻辑：

1. 排序：按区间 左端点 从小到大排序。
2. 遍历合并：
   • 初始化结果列表，放入第一个区间。
   • 遍历后续区间：
     • 若当前区间的 start 小于等于 结果列表中最后一个区间的 end → 重叠，更新最后一个区间的 end 为 max(原end, 当前end)。
     • 否则 → 不重叠，直接将当前区间加入结果列表。

import java.util.*;class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) return new int[0][];// ⚠️ [核心逻辑 1] 按左端点升序排序Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {int L = interval[0], R = interval[1];// ⚠️ [核心逻辑 2] 判断是否重叠// 如果列表为空，或者当前区间的左端点 > 上一个区间的右端点 -> 不重叠if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {// ⚠️ [核心逻辑 3] 重叠，合并：更新右端点为最大值merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}

---

🔄 变体 1：LeetCode 57. 插入区间 (Insert Interval)

题目内容：给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi]。在列表中插入一个新的区间 newInterval，你需要确保列表中的区间仍有序且不重叠（必要时合并区间）。
相比母题的变化：

1. 输入特性：原列表已经有序且无重叠。
2. 策略选择：
   • 方法 A (复用合并逻辑)：将 newInterval 加入列表，重新排序，然后直接调用“合并区间”的逻辑。代码最简洁，但时间复杂度略高（$O(N \log N)$）。
   • 方法 B (一次遍历)：利用原列表有序的特性，分三段处理（$O(N)$）：
     1. 左边不重叠：interval.end < newInterval.start，直接加入结果。
     2. 中间重叠：interval.start <= newInterval.end，合并更新 newInterval 的边界。
     3. 右边不重叠：interval.start > newInterval.end，将合并后的 newInterval 加入结果，然后把剩余所有区间加入。
3. 代码展示：这里展示更高效的 方法 B。

import java.util.*;class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> result = new ArrayList<>();int i = 0;int n = intervals.length;// ⚠️ [变化点 1] 阶段一：添加所有在新区间左边且不重叠的区间while (i < n && intervals[i][1] < newInterval[0]) {result.add(intervals[i]);i++;}// ⚠️ [变化点 2] 阶段二：合并所有与新区间重叠的区间// 只要当前区间的 start <= newInterval 的 end，就说明重叠while (i < n && intervals[i][0] <= newInterval[1]) {newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}// 将合并后的新区间加入result.add(newInterval);// ⚠️ [变化点 3] 阶段三：添加所有在新区间右边且不重叠的区间while (i < n) {result.add(intervals[i]);i++;}return result.toArray(new int[result.size()][]);}
}

---

🔄 变体 2：LeetCode 452. 用最少数量的箭引爆气球 (Minimum Number of Arrows to Burst Balloons)

题目内容：有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 中，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若 xstart <= x <= xend，则该气球会被引爆。求引爆所有气球所需的最小弓箭数。
相比母题的变化：

1. 目标变化：不是合并区间，而是寻找最少的点，使得每个区间内至少有一个点。
2. 贪心策略：
   • 排序：按 右端点 (end) 升序排序（这是关键！）。
   • 逻辑：
     • 第一支箭射在第一个气球的 右端点（为了尽可能覆盖后面开始的气球）。
     • 遍历后续气球：
       • 若当前气球的 start > 当前箭的位置 → 射不到，需要新箭。新箭位置设为当前气球的 右端点，箭数 +1。
       • 若 start <= 当前箭的位置 → 能被同一支箭射爆（因为已按右端点排序，当前气球右端点肯定 >= 箭位置，只需关心左端点）。
3. 注意：本题等价于求“不重叠区间的数量”，但排序方式不同。

import java.util.*;class Solution {public int findMinArrowShots(int[][] points) {if (points.length == 0) return 0;// ⚠️ [变化点 1] 按右端点升序排序// 注意：使用 Integer.compare 防止减法溢出Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));int arrows = 1;int arrowPos = points[0][1]; // ⚠️ [变化点 2] 第一支箭射在第一个区间的右端点for (int i = 1; i < points.length; i++) {// ⚠️ [变化点 3] 判断是否重叠// 如果当前气球的左端点 > 箭的位置，说明射不到，需要新箭if (points[i][0] > arrowPos) {arrows++;arrowPos = points[i][1]; // 新箭射在当前气球的右端点}// 否则 (points[i][0] <= arrowPos)，说明当前箭能射爆这个气球，无需操作// 因为已按右端点排序，points[i][1] >= arrowPos，所以箭的位置不需要更新}return arrows;}
}