数据结构算法（合并区间集合元素的重叠区间）

LeetCode的悲惨刷题之旅—56.合并区间

      是一道middle难度的题，但大家不要怕，只要有二维数组基础就可以做出来。老规矩，让我们看一下题目：

英文版的：

      题就是这样的一道题，这道题是初高中的数学问题，就是区间的合并，如果两个区间能合并就合并，合并不了就直接输出区间，就像给的那两个例子一样。有的同学会问，那不是有很多种情况，实际上就是两种情况：

      1.当前区间的左端的值>结果集的最后一个区间的右端的值，就说明没办法合并，然后就直接把两个区间放入结果集当中。

      2.当前区间的左端的值<=结果集最后一个区间的右端的值，说明可以合并，然后选取当前区间的和后一个区间的右端的值的最大值，作为合并区间的右端值，这样结果集里形成了一个合并的区间

      在我们实现这些之前需要思考一些问题，我们无序的情况下，也是这两种情况么？当然不是的，无序时，我们的合并会有更多种情况，会让程序复杂化，所以我们要先排序，这里我们可以使用Comparator接口的静态方法comparingInt，然后用jdk8的特性Lambda表达式的写法往里面传值(intervals是二维数组)：

然后我们就可以写我们上面写的逻辑，首先，我们需要一个结果集，我们可以用一个List集合来作为存放结果集的容器，然后初始化结果集，把排序好的第一个区间放入结果集当中：

      然后我们开始遍历这个二维数组，去找能跟结果集的最后一个区间合并的区间，如果当前区间的左端的值大于结果集中最后一个区间的右端的值，就说明没有办法合并，就把这个集合放入结果集当中;反之，如果当前区间的左端的值小于等于结果集中的最后一个区间的右端的值，则说明可以合并区间，然后选出当前遍历到的区间和结果集最后一个区间的右端值的最大值，变成结果集中最后一个区间的新的右端值：

      最后把结果集变数组返回，就结束了：
      这道题的关键在于排序，很多人都想不到排序这一步，所以就会有很大的困扰，还有对于二维数组的理解不够深刻，不清楚怎么表示每一个位置，就很容易出错。

      我把完整的代码给大家，我这个解法不是最优解，如果有更好的算法，大家可以说一下。

public class Solution { public int[][] merge(int[][] intervals) { if(intervals.length<2){ return intervals; } Arrays.sort(intervals, Comparator.comparingInt(a->a[0])); List<int[]> res=new ArrayList<>(); res.add(intervals[0]); for(int i=1;i<intervals.length;i++){ if(intervals[i][0]>res.get(res.size()-1)[1]){ res.add(intervals[i]); }else{ res.get(res.size()-1)[1]=Math.max(intervals[i][1],res.get(res.size()-1)[1]); } } return res.toArray(new int[res.size()][]); } } 

本文地址：https://blog.csdn.net/weixin_44122231/article/details/108042812