力扣56-合并区间（Java详细题解）

题目链接：56. 合并区间 - 力扣（LeetCode）

前情提要：

在刷本题前建议刷一下力扣452-用最少数量的箭引爆气球和力扣435-无重叠区间。

452题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode） 题解链接：力扣452-用最少数量的箭引爆气球（Java详细题解）-CSDN博客

435题目链接:. - 力扣（LeetCode） 题解链接：力扣435-无重叠区间（Java详细题解）-CSDN博客

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法：局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪心来试试。

题目思路：

当你刷完力扣452和力扣435时，会发现这俩题很相似，都是求重叠区间，只是对重叠区间的处理逻辑不一样。

本题的处理逻辑就是将重叠的区间进行合并。

所以本题局部最优：遇到重叠的区间就进行合并。

全局最优：得到一个不重叠的区间数组。

想要得到尽可能的重叠区间，首先我们先对区间数组根据左边界进行升序排序。

那么怎么将遇到的区间进行合并呢？

其实处理当前遍历的区间和上一个区间的左右区间就可以了。

如果当前区间的左区间小与等于上一个区间的右区间，那么这俩个区间一定重叠。

此时我们应该直接对结果集进行处理，将右边界取当前区间和上一个区间的最大值。

为什么取最大值，因为题目要求出合并的区间，那么右边界一定要是最大那个区间右边界。而合并后的左边界就是上一个区间的左边界。

为啥左边界是上一个区间的左边界，因为我们是按左边界来进行排序的，上一个区间的左边界肯定小与等于下一个遍历的左边界。

那么我们合并区间的逻辑就处理完了，接下来我们开看看代码。

最终代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        //该题与前俩个题很类似
        //题目要求我们合并所有重叠的区间，所以我们要找出所有重叠的区间，并将重叠的区间的左右边界进行处理
        //怎么处理这个左右边界很重要
        //对原数组进行处理很难，不仅要合并数组，还要删除数组
        //这里有一个代码技巧
        //所以我们再新建一个结果集 收集我们的结果
        //同时 我们在遍历数组的时候 并不断的对我们的结果集进行修改
        List<int []> result = new ArrayList<>();
        Arrays.sort(intervals,(a,b) -> {
            return a[0] - b[0];
        });
        //题目要求区间数组不为空 我们直接将第一个区间放入我们的结果集 然后再遍历我们的区间数组
        //再不断的修改我们的结果集
        //因为我们是从i=1开始遍历我们的区间数组，如果我们不把i = 0放进我们的结果集就会出现一些问题，比如没有把第一个区间数组漏掉了。
        result.add(intervals[0]);
        for(int i = 1;i < intervals.length;i ++){
            //遇到了重叠的区域
            //在这里我们直接修改结果集
            //因为我们先按照左边界 从小到大排序 
            //所以左边界最小值肯定是i - 1的左边界
            //而右边界不一定 所以此时我们要让我们的结果集的右边界取一个最大值
            if(intervals[i][0] <= result.getLast()[1]){
                result.getLast()[1] = Math.max(intervals[i][1],result.getLast()[1]);
            }else{
                //没有遇到重叠的直接放进结果集就可以
                result.add(intervals[i]);
            }
            
        }
        return result.toArray(new int[result.size()][]);
    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！