//先排序，将左区间小的放在前面，然后如果前一个的右区间大于下一个的左区间，则可以合并，分别用两个下标指向当前的大区间和将要考察的小区间
class Solution { public int[][] merge(int[][] intervals) { if(intervals.length<=1) return intervals; quickSort(intervals,0,intervals.length-1); int j=0; for(int i=0;i<intervals.length;i++) { if(intervals[j][1]>=intervals[i][0]) { intervals[j][1]=Math.max(intervals[j][1],intervals[i][1]); } else { j++; intervals[j][0]=intervals[i][0]; intervals[j][1]=intervals[i][1]; } } int[][] res = Arrays.copyOfRange(intervals, 0, j+1); return res; } public void quickSort(int[][] arr,int l,int r) { if(l>=r) return ; int p=partition(arr,l,r); //执行partition操作将数组分成两份 quickSort(arr,l,p-1); quickSort(arr,p+1,r); } public int partition(int[][] arr,int l,int r) { int v=arr[l][0]; int i=l; //[l-i]为左半部分 初始为0，小于i的部分包括i for(int k=l+1;k<=r;k++) { if(arr[k][0]<v) { swap(arr,k,i+1); i++; } } swap(arr,l,i); return i; } public void swap(int[][] arr,int i,int j) { int temp=arr[i][0]; arr[i][0]=arr[j][0]; arr[j][0]=temp; int y=arr[i][1]; arr[i][1]=arr[j][1]; arr[j][1]=y; }}
转载于:https://www.cnblogs.com/cold-windy/p/11205287.html
相关资源：日期合并算法