【手撕真题】合并区间

题目意思很好理解给定一个区间集合每个区间由 [start, end] 组成要求合并所有重叠的区间返回一个不重叠的区间数组且这个数组要恰好覆盖输入中的所有区间。思路首先先按每个区间的起始值从小到大排序这样重叠的区间就会挨在一起方便后续合并然后初始化一个结果列表把排序后的第一个区间放进去作为初始的待合并区间接着遍历剩下的所有区间每次取出结果列表的最后一个区间和当前区间比较如果当前区间的起始值小于等于最后一个区间的结束值说明两个区间重叠就把最后一个区间的结束值更新为两者的最大值完成合并如果不重叠就直接把当前区间加入结果列表最后把结果列表转换成二维数组返回即可。代码实现publicint[][]merge(int[][]intervals){// 区间个数为0或1直接返回if(intervals.length1){returnintervals;}// 1. 按区间的start值从小到大排序// a[0]-b[0]表示按start升序Arrays.sort(intervals,(a,b)-a[0]-b[0]);// 2. 初始化结果列表存储合并后的区间Listint[]resnewArrayList();// 先将排序后的第一个区间加入结果列表作为初始合并区间res.add(intervals[0]);// 3. 遍历剩下的所有区间逐个合并for(inti1;iintervals.length;i){// 取出结果列表中最后一个区间int[]lastres.get(res.size()-1);// 取出当前遍历的区间int[]currintervals[i];// 判断是否重叠当前区间的start 最后一个区间的endif(curr[0]last[1]){// 重叠合并区间更新最后一个区间的end为两者最大值last[1]Math.max(last[1],curr[1]);}else{// 不重叠直接将当前区间加入结果列表res.add(curr);}}// 4. 将Listint[]转换为int[][]returnres.toArray(newint[res.size()][]);}