一、题目要求

以数组 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

二、解法1-排序 O(Nlogn) 执行时间长，内存消耗高

先按照每个区间的第一个数字给 intervals排序，顺序是由小到大，需要自己写一个比较器

然后将第一个区间放到一个暂存器 _ret 中。

如果intervals只有一个区间，无需处理，直接返回即可。

如果下一个区间的左小于等于 _ret中的区间的右，两个区间就可以合并，新区间的左不变，右取最大值。

如果下一个区间的左大于 _ret中的区间的右，说明两个区间不重叠，不能合并，将 _ret中的区间放入答案中，然后 _ret赋值为该区间进行下一次合并。

如果_ret已经与最后一个区间进行判断了，无论如何，_ret中的都是最后一个区间了（_ret的右都是最大的了），直接把_ret放入答案中。

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if(intervals.size()==1)return intervals;sort(intervals.begin(),intervals.end());vector<vector<int>> ret;vector<int> _ret = intervals[0];int falt = 0;for (int i = 0; i < intervals.size() - 1; i++) {if (_ret[1] >= intervals[i + 1][0]) // 合并区间{_ret[1] = max(intervals[i + 1][1],_ret[1]);} else {ret.emplace_back(_ret);_ret = intervals[i + 1];}if (i + 1 == intervals.size() - 1) {ret.emplace_back(_ret);break;}}return ret;}
};

三、解法2-思路优化版

解法2是解法1的思路优化版，执行时间几乎没有改变，但是内存消耗一般，而且更加通俗易懂：

首先，两个区间的相互关系有三种情况：

         可以发现，只要是上两种情况，就一定有：R>= l && L <= r。（两种情况取交集）

        只有满足 R>= l && L <= r 的两个区间才重合，才需要合并，所以遍历数组，只要满足上式，就合并区间，左边界取最小值，右边界取最大值

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end()); // 先排序vector<vector<int>> ret{intervals[0]};for (const auto& LR : intervals) {int i = 0;for (; i < ret.size(); i++) {if (LR[1] >= ret[i][0] && LR[0] <= ret[i][1]) {ret[i][0] = min(ret[i][0], LR[0]);ret[i][1] = max(ret[i][1], LR[1]);break;}}if (i == ret.size()) // 没有可以合并的区间ret.emplace_back(LR);}return ret;}
};