题解 | #合并区间#

合并区间

http://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a

一.题目描述
NC37合并区间:
题目链接：https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6atpId=196&&tqId=37071&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一组区间，请合并所有重叠的区间，请保证合并后的区间按区间起点升序排列。
二.算法(贪心)
图片说明
1、将每个区间按左端点从小到大进行排序
2、如图所示，可分3种情况
情况一：当前区间完全被上一区间覆盖，直接跳过
情况二：将当前区间的右端点更新为上一区间的右端点，达到区间延长的效果
情况三：当前区间的左端点严格大于上一区间的右端点，则表示该区间不能合并，更新区间
下面是代码：

#include<algorithm>
bool cmp(Interval a,Interval b){//sort的比较函数
     if(a.start==b.start){
         return a.end<b.end;     
     }
    return a.start<b.start;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> q;
        sort(intervals.begin(), intervals.end(),cmp);
        int len=intervals.size();
        if(len==0) return intervals;
        for(int i=1;i<len;i++){
            if(intervals[i].start <= intervals[i-1].end){
                    //区间的合并
                    intervals[i].start = min(intervals[i-1].start,intervals[i].start);
                    intervals[i].end = max(intervals[i-1].end,intervals[i].end);
                } else{
                    //将合并好的区间放入
                     q.push_back(intervals[i-1]);
                }
        }
        q.push_back(intervals[len-1]);//最后一个区间放入
        return q;
    }
};

时间复杂度：O(n) 只需要进行排序后对所有区间进行一次遍历
空间复杂度：O(n) 需要额外开辟空间
优缺点：写起来简单,容易实现
三.算法(排序)
我们用数组ans存储最终的答案。首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：如果当前区间的左端点在数组ans中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组ans的末尾；否则，它们重合，我们需要用当前区间的右端点更新数组ans中最后一个区间的右端点，将其置为二者的较大值。

#include<algorithm>
bool cmp(Interval a,Interval b){//sort的比较函数
     if(a.start==b.start){
         return a.end<b.end;     
     }
    return a.start<b.start;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),cmp);//排序
         vector<Interval>ans;//返回的结果数组
         int i = 0,n = intervals.size();
         int l,r;
         while(i < n){
              l = intervals[i].start;//用来表示当前区间左端的指针
              r = intervals[i].end; //用来表示当前区间右端的指针
             while(i<n-1&&r>=intervals[i+1].start){//合并区间
                 i++;//指针后移
                 r=max(r,intervals[i].end);
             }
             //将当前合并完的区间进行插入
             ans.push_back({l,r});
             i++;//指针后移
         }
         return ans;
    }
};

时间复杂度:O(n) 利用双指针将所有区间遍历
空间复杂度:O(n) 需要额外开辟空间来返回结果
优缺点：时间复杂度相比较算法二低一点，但是写起来麻烦