一、56. 合并区间

🔗 题目链接：LeetCode 56. 合并区间

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

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

🧠 思路分析
区间类贪心问题的核心套路：先排序，再遍历合并。
统一将所有区间按照左端点升序排列，保证能重叠的区间一定连续排布。
依次遍历区间，维护结果集合：结果为空直接加入；当前区间与末尾区间发生重叠 / 接壤，更新末尾区间右端点为最大值；互不重叠则直接新增区间。
排序后单次线性遍历，逻辑极简，是所有区间题的基础模板。

💻 代码实现（C++）

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.empty()) return res;
        sort(intervals.begin(), intervals.end(), [](vector<int>& a,vector<int>& b){
            return a[0] < b[0];
        });
        res.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++){
            if(res.back()[1] >= intervals[i][0]){
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

📚 相关学习资源

• 文档：LeetCode 56. 合并区间 | 排序 + 贪心最优解全拆解 · 资源类型：CSDN · 2025-12-10 发布，从暴力解法优化到最优解，含图文演示和多语言实现

⏱ 复杂度分析
时间复杂度：O(nlog⁡n)O(nlogn)，主要消耗为排序操作，遍历为线性 O(n)O(n)。
空间复杂度：O(log⁡n)O(logn)，排序额外栈空间，不计结果返回数组。

---

二、57. 插入区间

🔗 题目链接：LeetCode 57. 插入区间

📝 题目描述
给你一个无重叠、按照区间起始端点排序的区间列表，以及一个待插入的新区间。要求插入后保持数组有序、区间互不重叠，重叠部分需要合并，最终返回完整区间列表。

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
解释：新区间与左侧区间重叠合并，右侧区间保持不变。

🧠 思路分析
本题是合并区间的进阶变种，原数组已有序且无重叠，无需重排。
整体分为三段处理：

1. 遍历收录所有右端点小于新区间左边界的区间，完全不影响；

2. 遍历所有和新区间重叠的区间，不断收缩更新新区间的左右边界，完成合并；

3. 收录所有左边界大于新区间右边界的右侧区间。
   最后拼接 左段 + 合并后新区间 + 右段，一次遍历即可完成，效率极高。

💻 代码实现（C++）

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size();
        int i = 0;
        while(i < n && intervals[i][1] < newInterval[0]){
            res.push_back(intervals[i++]);
        }
        while(i < n && intervals[i][0] <= newInterval[1]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);
        while(i < n){
            res.push_back(intervals[i++]);
        }
        return res;
    }
};

📚 相关学习资源

• 文档：LeetCode 57：插入区间（Insert Interval）——一次遍历，把区间问题想清楚 · 资源类型：掘金 · 2026-02-05 发布，三段式处理逻辑清晰，分段思想讲解详细，新手友好

• 文档：【中等】力扣算法题解析LeetCode57：插入区间](https://blog.csdn.net/ylumwd/article/details/149478959) · 资源类型：CSDN · 2025-07-20 发布，含合并规则分析和多语言代码

• 文档：LeetCode第57题插入区间 · 资源类型：阿里云开发者社区 · 2024-08-16 发布于山东，包含「重组区间集再排序」与「不重组不排序」两种解法对比

⏱ 复杂度分析
时间复杂度：O(n)O(n)，仅需单次线性遍历所有区间。
空间复杂度：O(n)O(n)，存储最终结果数组。

---

三、452. 用最少数量的箭引爆气球

🔗 题目链接：LeetCode 452. 用最少数量的箭引爆气球

📝 题目描述
每个气球对应一个横向区间，竖直射箭，只要坐标落在区间内即可引爆气球。求解引爆全部气球，需要的最小弓箭数量。

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2

🧠 思路分析
经典区间选点贪心模型。最优策略：按区间右端点升序排序。
每次选择当前区间的右端点射箭，这个位置可以尽可能覆盖后续更多重叠气球。
遍历过程中，记录上一支箭的坐标；若当前气球左边界超出箭的位置，必须新增一支箭，并更新箭位为当前区间右端点。
和区间重叠类题目逻辑互通，是面试高频贪心原型题。

💻 代码实现（C++）

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty()) return 0;
        sort(points.begin(), points.end(), [](vector<int>& a,vector<int>& b){
            return a[1] < b[1];
        });
        int cnt = 1;
        int pos = points[0][1];
        for(auto& p : points){
            if(p[0] > pos){
                cnt++;
                pos = p[1];
            }
        }
        return cnt;
    }
};

📚 相关学习资源

• 文档：【码道初阶】国服ad两种殊途同归的贪心算法详解Leetcode452弓箭射气球问题](https://blog.csdn.net/qq_18944929/article/details/145412503) · 资源类型：CSDN · 2025-02-01 发布，提供两种不同循环写法，并揭示与 LeetCode 435 的异同

• 文档：【Leetcode刷题Python】452. 用最少数量的箭引爆气球](https://developer.aliyun.com/article/1577840) · 资源类型：阿里云开发者社区 · 2024-08-05 发布于北京，含 Python 实现和算法推

⏱ 复杂度分析
时间复杂度：O(nlog⁡n)O(nlogn)，排序为主要耗时。
空间复杂度：O(log⁡n)O(logn)，排序占用栈空间。

---

四、435. 无重叠区间

🔗 题目链接：LeetCode 435. 无重叠区间

📝 题目描述
给定一组区间，要求删除最少数量的区间，使得剩余所有区间完全互不重叠。端点相连不算重叠，例如 [1,2] 和 [2,3] 合法共存。

输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
输出：1
解释：删除 [1,3] 即可满足条件。

🧠 思路分析
和射气球为同源题型，解题目标相反：本题求「最少删除」等价于求「最多可选互不重叠区间」。
依旧采用右端点升序排序，优先选择结束更早的区间，留出更大空间给后续区间，选出最大合法集合。
最终答案 = 总区间数量 - 最多不重叠区间数量。

💻 代码实现（C++）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), [](vector<int>& a,vector<int>& b){
            return a[1] < b[1];
        });
        int select = 1;
        int last = intervals[0][1];
        for(auto& t : intervals){
            if(t[0] >= last){
                select++;
                last = t[1];
            }
        }
        return intervals.size() - select;
    }
};

📚 相关学习资源

• 文档：LeetCode 435 - 无重叠区间 · 资源类型：技术社区 · 2025-11-29 发布，包含 Swift 完整解法、代码逐行分析，以及会议室调度、排班系统等实际业务场景结合

• 文档：leetcode 435. 无重叠区间 · 资源类型：技术社区 · 2025-01-02 发布，含「换马甲」思维引导（课程安排 / 事件调度问题），C++ 实现及反证法证明

⏱ 复杂度分析
时间复杂度：O(nlog⁡n)O(nlogn)，由排序操作决定。
空间复杂度：O(log⁡n)O(logn)，排序额外空间。

---

结语

区间四道热题全部围绕「排序 + 贪心」展开，属于算法中套路极强的一类题型。

• 合并区间、插入区间 负责区间合并逻辑，

• 最少箭、无重叠区间 负责区间选点模型，

两两成对、相辅相成。吃透这四道题，遇到所有区间重叠、区间选择、区间合并类面试题都能快速套模板秒杀。

下一篇预告：

LeetCode 热题 100 精讲 | 链表环与交点篇：环形链表 II · 相交链表 · 回文链表 · 排序链表

持续更新连载。
如果本文对你有帮助，欢迎点赞、收藏、转发，你的支持是我持续创作的动力 ❤️

---

免责声明

本文仅供学习交流与算法思路分享，内容基于作者个人理解及公开资料整理。所有题目链接、资源文档均来源于互联网，版权归原作者所有。文章中的代码已在常见环境下验证，但不同环境或版本可能导致结果差异，请读者自行测试并谨慎参考。如有疑问或版权问题，请联系作者处理。