题目大意：
合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=56
解题思路分析：
本题需要先对数组进行一次排序，排序规则是区间开始坐标由小到大升序排序。排序后我们能够保证对于任意一个区间，它的开始坐标一定大于等于前区间的开始坐标，这样相邻2个区间的关系会有以下三种可能：
- 当前区间开始坐标大于前区间结束坐标，说明2区间不相交从而无法合并，将前区间加入返回结果。
- 当前区间开始坐标小于等于前区间结束坐标，说明2区间存在交集，交集范围是当前区间开始坐标到前区间结束坐标之间，此时可以合并，将前区间结束坐标更改为当前区间结束坐标。
- 当前区间结束坐标小于等于前区间结束坐标，说明当前区间是前区间的子集，当前区间可被忽略。
实现代码：
public int[][] merge(int[][] intervals) {
// 如果intervals为空，返回空
if(intervals.length==0) return new int[0][0];
// 按区间开始坐标升序排序
Arrays.sort(intervals, (x1, x2)->x1[0]-x2[0]);
// 返回结果
List<int[]> list = new ArrayList<>();
// 前区间
int[] pre = intervals[0];
// 从第二个区间开始循环与前区间比较
for(int i=1;i<intervals.length;i++){
// 当前区间
int[] current = intervals[i];
// 当前区间开始坐标大于前区间结束坐标，无交集
if(current[0] > pre[1]){
// 将前区间加入返回结果
list.add(pre);
// 将当前区间设置为前区间
pre=current;
}else if(current[1]>=pre[1]){
// 当前区间结束坐标大于等于前区间结束坐标
// 另外两个以确定条件：
// 1. 当前区间开始坐标小于等于前区间结束坐标（上面if的另外分支）
// 2. 当前区间开始坐标大于等于前区间开始坐标（因为排序）
// 此时2区间相交，将前区间结束坐标更改为当前区间结束坐标
pre[1]=current[1];
}
}
// 将最后一个区间加入返回结果
list.add(pre);
// 将list转化为数组返回
int[][] res = new int[list.size()][2];
for(int i=0;i<list.size();i++){
res[i] = list.get(i);
}
return res;
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 90.48% of Java online submissions for Merge Intervals.
Memory Usage: 40.9 MB, less than 63.77% of Java online submissions for Merge Intervals.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-56-merge-intervals-解题思路分析/