XingHuiSamaの宝藏之地

这几天的任务终于补完了，本来还打算一天两题的害，就这样吧

以数组 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] 可被视为重叠区间。

示例 3：

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

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

1. 核心思想：先排序，后合并

区间问题的难点在于区间可能是乱序的，导致我们不知道 [1, 5] 之后会不会突然冒出一个 [2, 3]。

排序的作用：通过 sort 默认的“字典序”排序，所有区间按照起点升序排列。
收益：排序后，如果我们发现当前区间的起点比前一个（已合并的）区间的终点还要大，那么当前区间及其之后的所有区间，都绝对不可能再与前面的区间产生重叠了。这让我们可以通过一次线性扫描就完成所有合并。

2. 逻辑拆解

初始化基准：先将 intervals[0] 压入结果集 mer。这是为了给循环提供一个“挡箭牌”，让后续区间都有对象可以比对。
重叠判定（>）：
- 情况 A（彻底断开）：intervals[i][0] > mer.back()[1]。说明当前会议开始时，上一个会议已经彻底结束了（连边界都没摸到）。此时直接作为新条目存入。
- 情况 B（发生重叠）：否则，说明两个会议时间有交叉（或者恰好首尾相接）。
合并的精髓（max）：在合并时，我们不能盲目相信当前区间的终点就是最长的。例如 [1, 10] 和 [2, 5]，合并后依然是 [1, 10]。因此必须使用 max(intervals[i][1], mid[1]) 来确保右边界只会向更长的地方延伸。

class 合并区间 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //先排序
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> mer;
        mer.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= mer.back()[1]) {
                mer.push_back(intervals[i]);
            }
            else {
                vector<int> mid = mer.back();//先弹出
                mer.pop_back();
                mer.push_back({mid[0], max(intervals[i][1],mid[1])});//然后合并
            }
        }
        return mer;
    }
};

3. 复杂度分析

时间复杂度：O**(NlogN)**。
- 排序耗时 O(NlogN)。
- 后续遍历数组仅需 O(N)。
- 总体受限于排序的复杂度。
空间复杂度：O**(logN) 或** O**(N)**。
- 除去存储答案的 mer 数组，主要是排序所需的栈空间。