每日算法-08

给出一个区间的集合，请合并所有重叠的区间。
示例 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) {
        if (null==intervals||intervals.length==0){
            return intervals;
        }
        int length = intervals.length;
        quickSort(intervals,0, length-1);
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);
        for (int i=1;i<length;i++) {
            int index = result.size() - 1;
            int[][] combine = combine(result.get(index),intervals[i]);

            if (combine.length==1){
                result.remove(index);
                result.add(combine[0]);
            }else{
                result.add(intervals[i]);
            }
        }
        int size = result.size();
        int[][] r = new int[size][2];
        for (int i=0;i<size;i++) {
            r[i] = result.get(i);
        }

        return r;

    }
    private int[][] combine(int[] a,int[] b){
        int al=a[0],ar=a[1],bl=b[0],br=b[1];
        if (ar>=bl ||bl<=ar){
            int[][] r = new int[1][2];
            r[0]=new int[]{al<bl?al:bl,br>ar?br:ar};
            return r;
        }else{
            int[][] r = new int[2][2];
            r[0]=a;
            r[1]=b;
            return r;
        }
    }
    private void quickSort(int[][] arr,int left,int right){
        if (left>=right){
            return;
        }
        int[] mid = arr[left];
        int i=left;
        int j=right;
        while (i<j){
            while (arr[j][0]>=mid[0]&&i<j){
                j--;
            }
            while (arr[i][0]<=mid[0]&&i<j){
                i++;
            }

            if (i<j){
                int[] tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        arr[left]=arr[i];
        arr[i]=mid;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);

    }
}