LeetCode 56 - 合并区间

思路

1. 排序：将所有区间按起始点从小到大排序。
2. 贪心合并：初始化一个结果列表，放入第一个区间。然后遍历剩余区间，将当前区间与结果列表中的最后一个区间比较：
   • 若重叠（当前区间起点 ≤ 结果区间终点），则更新结果区间的终点为两者终点的最大值。
   • 若不重叠，则将当前区间直接加入结果列表。

C++ 代码实现

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>> merged;merged.push_back(intervals[0]);for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] <= merged.back()[1]) {merged.back()[1] = max(merged.back()[1], intervals[i][1]);} else {merged.push_back(intervals[i]);}}return merged;}
};

注：sort 对于 vector<vector<int>> 默认按第一个元素排序，可省略 lambda。

复杂度

• 时间复杂度: O(n log n)，瓶颈在于排序。
• 空间复杂度: O(n)，用于存储返回结果。