56.合并区间

①根据区间的起始位排序
②遍历排序后的集合，当前区间和上一个区间比较起始位
	2.1 当前区间起始位大于上一个区间的起始位，区间不重合，放入结果集合中
	2.2 当前区间起始位小于等于上一个区间起始位，区间重合，重新计算上一个区间范围

这个快排当初考研的时候经常写，现在都不会了

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 1) return intervals;
        quickSort(intervals, 0, intervals.length - 1);
        List list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            if (list.size() == 0) {
                list.add(intervals[i]);
                continue;
            }
            int[] last = list.get(list.size() - 1);
            int[] cur = intervals[i];
            if (cur[0] > last[1]) {//区间不重合，放入结果集合
                list.add(cur);
                continue;
            }
            list.remove(list.size() - 1);//删除上一个区间范围
            list.add(new int[]{Math.min(cur[0], last[0]), Math.max(cur[1], last[1])});//重新计算区间范围
        }
        return list.toArray(new int[list.size()][]);
    }
    private void quickSort(int[][] array, int begin, int end) {
        if (begin >= end) return;
        int low = begin, high = end;
        int[] cur = array[low];
        boolean direction = true;
        out:
        while (low < high) {
            if (direction) {
                for (int i = high; i >= low; i--) {
                    if (array[i][0] < cur[0]) {
                        array[low] = array[i];
                        low++;
                        high = i;
                        direction = !direction;
                        continue out;
                    }
                }
                high = low;
            } else {
                for (int i = low; i <= high; i++) {
                    if (array[i][0] > cur[0]) {
                        array[high] = array[i];
                        high--;
                        low = i;
                        direction = !direction;
                        continue out;
                    }
                }
                low = high;
            }
        }
        array[low] = cur;
        quickSort(array, begin, low - 1);
        quickSort(array, low + 1, end);
    }
}