- 1、题目描述:
-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> &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 ++; } 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) -> (a.start - b.start));//按照区间的左端点排序 ArrayList<interval> res = new ArrayList<interval>(); int i = 0,n = intervals.size(); int l,r; while(i < n){ l = intervals.get(i).start;//用来存储当前区间的左端 r = intervals.get(i).end;//用来存储当前区间的右端 //合并区间 while(i < n-1 && r >= 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 };