合并区间，Merge Intervals

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

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

其中：

1 <= intervals.length <= 10^4

intervals[i].length == 2

0 <= starti <= endi <= 10^4

二、测试样例
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]]

说明：区间 [1,3] 和 [2,6] 重叠, 所以将它们合并为 [1,6]，合并后的区间没有重叠。

三、算法思路
本题是一道经典的贪心题目，首先，对区间按照每个区间的左值从小到大排序，排序后，相近的区间都在一块，然后，遍历一遍所有区间，有重叠和区间进行合并即可。

四、代码实现

class Solution {
public:
    vector<vector<int> > merge(vector<vector<int> >& intervals) {
        if(intervals.size() == 0) return {}; // 为空的情况
        sort(intervals.begin(), intervals.end()); // 以区间第一个元素为基准进行排序
        vector<vector<int> > ans;
        vector<int> tmp(intervals[0]);
        for(int i = 0; i < intervals.size(); ++i) { // 依次遍历
            auto value = intervals[i];
            if(tmp[1] < value[0]) {
                ans.push_back(tmp);
                tmp = value;
            } else if(tmp[1] <= value[1]){
                tmp[1] = value[1];
            }
        }
        ans.push_back(tmp);  // 别忘记最后一个区间
        return ans;
    }
};

五、复杂度分析
时间复杂度：O(nlogn)，排序的时间为 O(nlogn)，for 循环一遍的时间为 O(n)，故总的时间复杂度为O(nlogn)；

空间复杂度：O(n)，使用到一个临时的 vector 数组，故空间复杂度O(n)；

六、题目链接
https://leetcode-cn.com/problems/merge-intervals/

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬