56. 合并区间

1.题目描述及示例

题目描述 给出一个区间的集合，请合并所有重叠的区间。

示例

2.题解思路及代码

思路 先对二维数组按第一列元素升序排序，咋写的要记住，经常忘记，之后的思路和#26《删除排序数组中的重复项》差不多。

代码

public int[][] merge(int[][] intervals) { if (intervals.length<=1) return intervals; 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]; } }); int [][] newIntervals=new int[intervals.length][2]; int k=0,temp=0; for (int i=1;i<intervals.length;i++) { if (isOverLap(intervals[temp][0],intervals[temp][1],intervals[i][0],intervals[i][1])) { intervals[temp][1]=Math.max(intervals[temp][1],intervals[i][1]); } else { newIntervals[k][0]=intervals[temp][0]; newIntervals[k][1]=intervals[temp][1]; temp=i; k++; } } newIntervals[k][0]=intervals[temp][0]; newIntervals[k][1]=intervals[temp][1]; int [][] result=new int[k+1][2]; for (int i=0;i<k+1;i++) { result[i][0]=newIntervals[i][0]; result[i][1]=newIntervals[i][1]; } return result; } public boolean isOverLap(int l1,int r1,int l2,int r2) { if (l2<=r1) return true; return false; }