题目主要信息:

  • 给出一组区间,区间包括起始点,要求将重叠的区间合并
  • 重叠后的区间按照起点位置升序排列

具体思路:

  • step 1:既然要求重叠后的区间按照起点位置升序排列,我们就将所有区间按照起点位置先进行排序。使用sort函数进行排序,重载比较方式为比较interval结构的start变量。
  • step 2:排序后的第一个区间一定是起点值最小的区间,我们将其计入返回数组res,然后遍历后续区间。
  • step 3:后续遍历过程中,如果遇到起点值小于res中最后一个区间的末尾值的情况,那一定是重叠,取二者最大末尾值更新res中最后一个区间即可;如果遇到起点值大于res中最后一个区间的末尾值的情况,那一定没有重叠,后续也不会有这个末尾的重叠区间了,因为后面的起点只会更大,因此可以将它加入res。

具体过程可以参考如下图示: alt

代码实现:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool cmp(Interval &a, Interval &b) { //重载比较
        return a.start < b.start;
    }
    
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> res;
        if(intervals.size() == 0) //去除特殊情况
            return res;
        sort(intervals.begin(), intervals.end(), cmp); //按照区间首排序
        res.push_back(intervals[0]); //放入第一个区间
        for(int i = 1; i < intervals.size(); i++){ //遍历后续区间,查看是否与末尾有重叠
            if(intervals[i].start <= res.back().end) //区间有重叠,更新结尾
                res.back().end = max(res.back().end, intervals[i].end);
            else //区间没有重叠,直接加入
                res.push_back(intervals[i]);
        }
        return res;
    }
};

复杂度分析:

  • 时间复杂度:O(nlog2n)O(nlog_2n),排序的复杂度为O(nlog2n)O(nlog_2n),后续遍历所有区间的复杂度为O(n)O(n),属于低次幂
  • 空间复杂度:O(1)O(1),res为返回必要空间,没有使用额外辅助空间