LeetCode刷题复盘笔记—一文搞懂贪心算法之56. 合并区间（贪心算法系列第十四篇）

今日主要总结一下可以使用贪心算法解决的一道题目，56. 合并区间

题目：56. 合并区间

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

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

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

本题重难点

这道题主要就分为三种情况：

1. 一个区间包含另一个区间
2. 两个区间有交集
3. 两个区间没有交集

写法一：

C++代码

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(), intervals.end());for(int i = 0; i < intervals.size(); i++){int start = intervals[i][0], end = intervals[i][1];while(i < intervals.size() - 1 &&  end >= intervals[i + 1][0]){end = max(end, intervals[i + 1][1]);start = min(start, intervals[i + 1][0]);i++;}res.push_back({start, end});}return res;}
};

写法二：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(), intervals.end());res.push_back(intervals[0]);for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] <= res.back()[1]){ // 出现重叠\// 合并区间// 此时由于已经按照左边界排好序，intervals[i - 1][0] 一定<intervals[i][0]// 所以只需要更新右边界res.back()[1] = max(res.back()[1], intervals[i][1]);}else{res.push_back(intervals[i]);}}return res;}
};

以上两种写法都可以，看哪个容易理解会写一种写法就行！

---

总结

这道题主要就分为三种情况：

1. 一个区间包含另一个区间
2. 两个区间有交集
3. 两个区间没有交集

本文给出了两种写法，大家看哪个容易理解会写一种写法就行！
但这道题目本质上还是区间重叠问题的加强版，欢迎大家关注本人公众号：编程复盘与思考随笔(关注后可以免费获得本人在csdn发布的资源源码)