区间集合

🧩 一、什么是「区间集合」问题？

在 LeetCode 上，「区间集合」问题通常是指：

给定若干个区间（形如 [start, end]），让你去合并、插入、统计重叠、计算空隙、或选择最大不重叠子集等操作。

例如：

输入：[[1,3], [2,6], [8,10], [15,18]]
输出：[[1,6], [8,10], [15,18]]

这就是经典的“区间合并”问题。

---

🧠 二、常见的区间题目类型（按思维模式分）

类别	典型问题	主要操作思维	常用算法
① 区间合并	LC56、LC57、LC435	合并重叠区间	排序 + 线性扫描
② 插入区间	LC57	插入并合并	同样是排序 + 合并逻辑
③ 区间交集	LC986	找两个集合的交集	双指针
④ 区间去重 / 选择	LC435、LC452	选出最大不重叠集合	贪心（按end排序）
⑤ 区间覆盖	LC1288、LC1024	选最少区间覆盖一段范围	贪心（扫描法）
⑥ 区间差集	LC1272	从区间集合中删除一段区间	扫描判断交集部分
⑦ 区间调度 / 会议室	LC253、LC759	判断重叠次数或所需资源数	最小堆 / 扫描线
⑧ 区间计数 / 差分	LC715、LC370	多次增删统计	差分数组 / 有序表

---

⚙️ 三、通用套路与思路总结

🪜 Step 1：排序（关键）

几乎所有区间问题的第一步都是：

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

按起点排序后，我们才能保证线性遍历时相邻区间可直接比较是否重叠。

---

🪜 Step 2：判断重叠条件

两个区间 [a1, a2] 与 [b1, b2] 的关系：

关系	条件	说明
重叠	b1 <= a2	右边的起点 ≤ 左边的终点
不重叠	b1 > a2	右边的起点在左边之后

重叠 → 合并：merged = [a1, max(a2, b2)]

---

🪜 Step 3：合并 or 插入 or 统计

核心逻辑通常长这样👇：

List<int[]> res = new ArrayList<>();
Arrays.sort(intervals, (a,b)->a[0]-b[0]);

int[] cur = intervals[0];
for (int i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= cur[1]) {
        // 重叠 -> 合并
        cur[1] = Math.max(cur[1], intervals[i][1]);
    } else {
        // 不重叠 -> 保存旧区间
        res.add(cur);
        cur = intervals[i];
    }
}
res.add(cur);
return res;

---

💡 四、重点题型详解

1️⃣ 区间合并（LC56）

题意：
合并所有重叠区间。

解法：
排序 + 一次扫描
→ 如果下一个区间的 start <= 当前end 就合并，否则输出当前区间。

---

2️⃣ 插入区间（LC57）

题意：
在一组非重叠区间中插入一个新的区间，并返回合并后的结果。

思路：

• 先把所有在新区间左边的加进去；
• 再合并所有与新区间重叠的；
• 最后把右边剩余区间加进去。

代码：

List<int[]> res = new ArrayList<>();
for (int[] cur : intervals) {
    if (cur[1] < newInterval[0]) res.add(cur); // 在左边
    else if (cur[0] > newInterval[1]) {        // 在右边
        res.add(newInterval);
        newInterval = cur;
    } else {                                   // 重叠
        newInterval[0] = Math.min(newInterval[0], cur[0]);
        newInterval[1] = Math.max(newInterval[1], cur[1]);
    }
}
res.add(newInterval);
return res;

---

3️⃣ 区间交集（LC986）

思路：
双指针法同时遍历两个有序区间集合：

• 如果有重叠，就取交集；
• 谁的 end 小，谁往后移动。

---

4️⃣ 不重叠区间数量（LC435）

思路：
按 end 升序排序，贪心选区间，尽可能早结束。

模板：

Arrays.sort(intervals, (a,b)->a[1]-b[1]);
int count = 1, end = intervals[0][1];
for (int i = 1; i < n; i++) {
    if (intervals[i][0] >= end) {
        count++;
        end = intervals[i][1];
    }
}

👉 这类题常用在会议室安排、活动选择问题中。

---

5️⃣ 区间覆盖问题（LC1024、LC1288）

问题本质：
选最少区间使得 [0, T] 被完全覆盖。

技巧：

• 按起点排序；
• 每次选择在当前可达范围内右端点最大的区间（贪心扩展）。

---

6️⃣ 区间调度最小会议室数（LC253）

方法一：最小堆
每次放入会议，若最早结束时间 ≤ 新会议开始，就可以复用。

方法二：扫描线（推荐）
把所有 start 记为 +1，end 记为 -1，排序扫描求最大并发数。

---

🧮 五、通用算法模板总结

场景	模板思维	算法
合并重叠	排序 + 线性扫描	O(n log n)
插入并合并	分类：左、右、重叠	O(n)
区间交集	双指针	O(n + m)
不重叠最大数量	按结束时间贪心	O(n log n)
区间覆盖	扫描线/贪心	O(n log n)
多会议室数	扫描线 / 最小堆	O(n log n)

---

🔍 六、思维图（文字版）

区间集合问题
├── 基础型
│   ├── 合并区间（56）
│   └── 插入区间（57）
├── 交集型
│   ├── 两集合交集（986）
│   └── 区间差集（1272）
├── 贪心型
│   ├── 不重叠最大数（435）
│   └── 区间覆盖最小数（1024/1288）
└── 扫描线型
    ├── 会议室数（253）
    └── 最大并发数统计

---

🧱 七、典型陷阱

1. 边界判断混乱

   • [start, end] 是闭区间？半开区间？
   • 如果题目没说，通常默认闭区间。

2. 忘记加最后一个区间

   • 合并完循环后，别忘 res.add(cur)

3. 不排序就直接遍历

   • 绝大多数题都必须排序。

4. 重叠判断条件错

   • 一定是 next.start <= cur.end 才算重叠。

---

🧭 八、进阶方向

• 支持动态插入删除区间（例如 LeetCode 715 Range Module）
• 使用「线段树 / 平衡树」维护动态区间
• 区间和差分统计（370, 1094）