关于算法:合并区间leetcode56

题目形容

给出一个区间的汇合，请合并所有重叠的区间。

示例 1:

输出: [[1,3],[2,6],[8,10],[15,18]]
输入: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

崩溃思路

一、先排序，后交加

1、先将数值依照左侧数值进行升序排列，雷同的依照第二个数的升序排列，应用 Arrays.sort(), 重写下 comprator 即可
2、从做开始，进行合并，因为曾经进行了右边数值的排序，而对单个数组而言，右边的数值肯定是小于或者等于左边的数值的，所以只有比拟左边数值和下一个数组的右边数值的大小，即可判断是否有交加
3、对有交加的数值，取两个数组的右边值的最小值和左边值的最大值
4、将组合后的数组返回

二、双循环比照取交加

1、第一个数组，按从左到右，和前面的数组比照
2、如果存在交加，则合并
3、将合并后的数值放到前面数组的地位，而后将后面数组置为 null，同时完结本轮循环，进入下一次循环
4、循环遍历完后，将非 null 的数组取出回传

波及的办法

 Arrays.sort(intervals, new Comparator<int[]>(){public int compare(int[] o1, int[]o2){if(o1[0] == o2[0]){return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        })

vscode 代码链接

https://github.com/lunaDolphin/leetcode/tree/master/queueMerge56
https://github.com/lunaDolphin/leetcode/tree/master/queueMerge56_1