NC37:合并区间

NC37:合并区间

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=117&&tqId=34958&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

-3、 设计思想：

详细操作流程看下图

- 代码：
c++版本:

/**
 * 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(const Interval &a,const Interval &b){
        return (a.start<b.start); 
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),cmp);//排序
         vector<Interval>res;//返回的结果数组
         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);
             }
             //将当前合并完的区间进行插入
             res.push_back({l,r});
             i ++;
         }