mergeIntervals

56. mergeIntervals

分析

排序：
- 首先将所有区间按照起始值从小到大排序。排序后，若两个区间有重叠，它们一定是相邻的
遍历与合并：
- 用变量 l 和 r 分别表示当前合并区间的起始和结束
- 遍历排序后的区间：
  - 如果当前遍历区间的起始值大于当前合并区间的结束值 r，说明当前区间与前面的合并区间没有重叠，应将前面的合并区间加入结果，并更新 l 和 r
  - 如果有重叠，则将 r 更新为当前区间结束值的较大值
- 遍历结束后，将最后一个合并区间加入结果

时间复杂度

排序：O(nlogn) ，n 是区间的数量
遍历：O(n)，每个区间只会被处理一次

总时间复杂度为 O(nlogn)

空间复杂度

排序所需的额外空间复杂度为 O(logn) （排序算法的递归栈空间）
结果存储的空间复杂度为 O(n)

总空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        vector<vector<int>> res; // 用于存储最终结果

        if (intervals.empty()) return res; // 如果输入为空，直接返回空数组

        // 1. 按区间的起始值排序
        sort(intervals.begin(), intervals.end());

        // 2. 初始化合并区间的左右边界
        int l = intervals[0][0], r = intervals[0][1];

        // 3. 遍历剩余区间
        for (int i = 1; i < intervals.size(); ++ i) {
            // 当前区间的起始值 > 当前合并区间的结束值，说明没有重叠
            if (r < intervals[i][0]) {
                res.push_back({l, r});  // 将当前合并区间加入结果
                l = intervals[i][0];   // 更新新的合并区间的起始值
                r = intervals[i][1];   // 更新新的合并区间的结束值
            } else {
                // 如果有重叠，则更新当前合并区间的结束值
                r = max(r, intervals[i][1]);
            }
        }

        // 将最后一个合并区间加入结果
        res.push_back({l, r});

        return res;
    }
};