输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Solution {
        public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        //循环循环遍历我的
        if (null == intervals || intervals.length < 1) {
            return new int[0][];
        } else {
            qSort(intervals, 0, intervals.length - 1);
            int[] temp = intervals[0];
            for (int i = 1; i < intervals.length; i++) {
                if (intervals[i][0] <= temp[1]) {
                    temp[1] = intervals[i][1] > temp[1] ? intervals[i][1] : temp[1];
                } else {
                    list.add(temp);
                    temp = intervals[i];
                }
            }
            if (list.size() > 0) {
                if (list.get(list.size() - 1)[1] < temp[0]) {
                    list.add(temp);
                }else {
                    int[] ints = list.get(list.size() - 1);
                    list.remove(list.size() - 1);
                    ints[1]=ints[1] > temp[1] ? ints[1] : temp[1];
                    list.add(ints);
                }
            } else {
                list.add(temp);
            }
            int[][] returnArr = new int[list.size()][];
            for (int i = 0; i < returnArr.length; i++) {
                returnArr[i] = list.get(i);
            }
            return returnArr;
        }
    }
    private void qSort(int[][] arr, int l, int r) {
        int partition = getPartition(arr, l, r);
        if (-1 != partition) {
            qSort(arr, l, partition - 1);
            qSort(arr, partition + 1, r);
        }
    }
    private int getPartition(int[][] arr, int l, int r) {
        if (r - l < 1) {
            return -1;
        } else {
            int[] temp = arr[l];
            while (l < r) {
                while (l < r && arr[r][0] >= temp[0]) r--;
                arr[l] = arr[r];
                while (l < r && arr[l][0] <= temp[0]) l++;
                arr[r] = arr[l];
            }
            arr[r] = temp;
            return r;
        }
    }
}