企业官网建设流程全解析

一、 题目来源与描述

题目来源：LeetCode 第 56 题 - 合并区间 (Merge Intervals)

难度：中等

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

二、 输入数据结构深度解析

在解答本题前，我们需要明确输入数据的结构。题目给出的输入 intervals 其实是一个二维数组（在 C++ 中为二维向量vector<vector<int>>）。

外层维度：表示有多少个区间。例如 intervals.size() 代表区间的总个数。

内层维度：固定长度为 2。intervals[i][0] 代表第 i 个区间的左端点（起始位置），intervals[i][1] 代表第 i 个区间的右端点（结束位置）。

示例解析：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
这代表集合中有 4 个区间：

1. 区间 1：从 1 到 3
2. 区间 2：从 2 到 6
3. 区间 3：从 8 到 10
4. 区间 4：从 15 到 18

三、 核心算法思路：排序 + 贪心

这道题如果直接两两比较，时间复杂度会非常高。最优的解法基于一个关键的预处理步骤：排序。

1.为什么需要排序？

如果区间是无序的，比如 [[8,10], [1,3], [2,6]]，我们很难判断 [1,3] 和 [2,6] 是否重叠，因为它们不相邻。但如果我们按区间的左端点进行升序排序，数组就会变成 [[1,3], [2,6], [8,10]]。
此时，我们只需要从左到右遍历一次，比较当前区间与前一个已合并区间的关系即可。

2.贪心策略与合并逻辑

排序后，我们维护一个结果数组 merged。遍历排序后的区间，对于每一个当前区间 curr，与 merged 中的最后一个区间 last 进行比较：

情况 A：发生重叠（或相接）
如果 curr 的左端点≤last 的右端点（即 curr[0] <= last[1]），说明两个区间有交集。
操作：更新 last 的右端点，取两者右端点的最大值：last[1] = max(last[1], curr[1])。
(注意：这里不需要更新左端点，因为我们已经按左端点排序，last的左端点一定小于等于curr的左端点)

情况 B：没有重叠
如果 curr 的左端点>last 的右端点（即 curr[0] > last[1]），说明两个区间完全分离。
操作：直接将 curr 加入 merged 数组，成为新的 last。

3.算法流程图解

以 intervals = [[1,3],[2,6],[8,10],[15,18]] 为例：

排序：已经是升序。

初始化：merged = [[1,3]]

遍历[2,6]：2 <= 3 (重叠) -> 更新 merged 末尾为 [1, max(3,6)] = [1,6]。此时 merged = [[1,6]]

遍历[8,10]：8 > 6 (不重叠) -> 直接加入。此时 merged = [[1,6], [8,10]]

遍历[15,18]：15 > 10 (不重叠) -> 直接加入。此时 merged = [[1,6], [8,10], [15,18]]

结束，返回 merged。

四、 C++ 代码实现

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

五、 复杂度分析

时间复杂度：O(NlogN)

主要消耗在排序上，C++ 的 std::sort 平均时间复杂度为O(NlogN)。

遍历合并的过程只需要一次线性扫描，时间复杂度为O(N)。

总体时间复杂度为O(NlogN)，其中N是区间的数量。

空间复杂度：O(logN)或O(N)

如果不考虑返回结果所占用的空间，主要取决于排序算法的递归栈空间，通常为O(logN)。

如果考虑返回结果 merged 数组，最坏情况下（所有区间都不重叠）需要存储N个区间，空间复杂度为O(N)。