【手撕真题】合并区间

题目意思很好理解：

给定一个区间集合，每个区间由 [start, end] 组成，要求合并所有重叠的区间，返回一个不重叠的区间数组，且这个数组要恰好覆盖输入中的所有区间。

思路

首先，先按每个区间的起始值从小到大排序，这样重叠的区间就会挨在一起，方便后续合并；

然后初始化一个结果列表，把排序后的第一个区间放进去，作为初始的待合并区间；

接着遍历剩下的所有区间，每次取出结果列表的最后一个区间和当前区间比较：

如果当前区间的起始值小于等于最后一个区间的结束值，说明两个区间重叠，就把最后一个区间的结束值更新为两者的最大值，完成合并；

如果不重叠，就直接把当前区间加入结果列表；

最后把结果列表转换成二维数组返回即可。

代码实现

publicint[][]merge(int[][]intervals){// 区间个数为0或1，直接返回if(intervals.length<=1){returnintervals;}// 1. 按区间的start值从小到大排序// a[0]-b[0]表示按start升序Arrays.sort(intervals,(a,b)->a[0]-b[0]);// 2. 初始化结果列表，存储合并后的区间List<int[]>res=newArrayList<>();// 先将排序后的第一个区间加入结果列表，作为初始合并区间res.add(intervals[0]);// 3. 遍历剩下的所有区间，逐个合并for(inti=1;i<intervals.length;i++){// 取出结果列表中最后一个区间int[]last=res.get(res.size()-1);// 取出当前遍历的区间int[]curr=intervals[i];// 判断是否重叠：当前区间的start <= 最后一个区间的endif(curr[0]<=last[1]){// 重叠：合并区间，更新最后一个区间的end为两者最大值last[1]=Math.max(last[1],curr[1]);}else{// 不重叠：直接将当前区间加入结果列表res.add(curr);}}// 4. 将List<int[]>转换为int[][]returnres.toArray(newint[res.size()][]);}