给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一：排序
class Solution {
public int[][] merge(int[][] intervals) {
int[][] tmp = new int[intervals.length][2];
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return a[0]-b[0];
}
});
int count = 0;
int i=0,j=0;
for(i = 0; i < intervals.length; i++){
int left = intervals[i][0];
int right = intervals[i][1];
for(j = i+1; j < intervals.length; j++){
if(intervals[j][0] > right) break;
if(right < intervals[j][1]) right = intervals[j][1];
}
tmp[count][0] = left;
tmp[count][1] = right;
count++;
i = j-1;
}
return Arrays.copyOfRange(tmp, 0, count);
}
}
解法二：标记法，速度快，不易理解
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
int count = 0;
for(int i = 0; i < len; i++) {
for(int j = i+1; j < len; j++){
if(isMerge(intervals, i, j)){
count++;
break;
}
}
}
int[][] res = new int[len-count][2];
count = 0;
for(int i = 0; i < len; i++){
if(intervals[i][0] == 1 && intervals[i][1] == -1) continue;
res[count] = intervals[i];
count++;
}
return res;
}
public boolean isMerge(int[][] intervals, int begin, int end) {
if(intervals[begin][0] == 1 && intervals[begin][1] == -1) return false;
if(intervals[end][0] == 1 && intervals[end][0] == -1) return false;
if(intervals[begin][0] < intervals[end][0] && intervals[begin][1] < intervals[end][0]) return false;
if(intervals[end][0] < intervals[begin][0] && intervals[end][1] < intervals[begin][0]) return false;
intervals[end][0] = Math.min(intervals[begin][0], intervals[end][0]);
intervals[end][1] = Math.max(intervals[begin][1], intervals[end][1]);
intervals[begin][0] = 1;
intervals[begin][1] = -1;
return true;
}
}