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、 设计思想：

详细操作流程看下图

-4、视频讲解链接B站视频讲解

- 代码：
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> &amp;intervals) {
        sort(intervals.begin(),intervals.end(),cmp);//排序
         vector<interval>res;//返回的结果数组
         int i = 0,n = intervals.size();
         int l,r;
         while(i &lt; n){
              l = intervals[i].start;//用来存储当前区间的左端
              r = intervals[i].end; //用来存储当前区间的右端
              //合并区间
             while(i &lt; n-1 &amp;&amp; r &gt;= intervals[i + 1].start){
                 i ++;
                 r = max(r,intervals[i].end);
             }
             //将当前合并完的区间进行插入
             res.push_back({l,r});
             i ++;
         }
         return res;
    }
};

Java版本：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<interval> merge(ArrayList<interval> intervals) {
        intervals.sort((a, b) -&gt; (a.start - b.start));//按照区间的左端点排序
        ArrayList<interval> res = new ArrayList<interval>();
        int i = 0,n = intervals.size();
        int l,r;
        while(i &lt; n){
             l = intervals.get(i).start;//用来存储当前区间的左端
             r = intervals.get(i).end;//用来存储当前区间的右端
              //合并区间
             while(i &lt; n-1 &amp;&amp; r &gt;= intervals.get(i + 1).start){
                 i ++;
                 r = Math.max(r,intervals.get(i).end);
             }
             //将当前合并完的区间进行插入
             res.add(new Interval(l, r));
             i ++;
         }
         return res;

    }
}

Python版本:

# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b

#
# 
# @param intervals Interval类一维数组 
# @return Interval类一维数组
#
class Solution:
    def merge(self , intervals ):
        # write code here
        intervals = sorted(intervals,key = lambda x : x.start) #按照区间的左端点排序
        res = [] #用来存储最终的结果
        i,n = 0,len(intervals)
        while i < n:
            l = intervals[i].start #用来存储当前区间的左端
            r = intervals[i].end #用来存储当前区间的右端
            #合并区间
            while i < n - 1 and r >= intervals[i + 1].start:
                i += 1
                r = max(r,intervals[i].end)
            #将当前合并完的区间进行插入
            res.append(Interval(l,r))
            i += 1
        return res

javaScript:

/*
 * function Interval(a, b){
 *   this.start = a || 0;
 *   this.end = b || 0;
 * }
 */

/**
 * 
 * @param intervals Interval类一维数组 
 * @return Interval类一维数组
 */
function merge( intervals ) {
    // write code here
    intervals.sort((a,b) => a.start - b.start);//按照区间的左端点排序
    let res = [];
    let i = 0,n = intervals.length;
    let l,r;
    while(i < n){
        l = intervals[i].start;//用来存储当前区间的左端
        r = intervals[i].end;//用来存储当前区间的右端
        //合并区间
        while(i < n-1 && r >= intervals[i+1].start){
            i ++;
            r = Math.max(r,intervals[i].end);
        }
        //将当前合并完的区间进行插入
        res.push(new Interval(l, r));
        i ++;
    }
    return res;
}
module.exports = {
    merge : merge
};