题目描述

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

示例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] 可被视为重叠区间。

思路

1.我们可以以二维数组的第一个元素为基准，进行快速排序，整理好二维数组。
2.然后以两个元素为一对遍历整个二维数组，判断二者是否应该被合并。
3.这里为了操作方便，使用ArrayList存储数组。

Java代码实现

    public int[][] merge(int[][] intervals) {
        List<int[]> arrays = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            arrays.add(intervals[i]);
        }

        quickSortArrays(arrays,0,arrays.size()-1);

        for (int i = 0; i < arrays.size()-1;) {
            int[] pre = arrays.get(i);
            int[] after = arrays.get(i+1);

            //如果after是pre的子集
            if(pre[1]>=after[1]){
                arrays.remove(i+1);
                continue;
            }

            //如果pre应该和after合并
            if(pre[1]>=after[0] && pre[1]<=after[1]){
                int[] nums = new int[]{pre[0],after[1]};
                arrays.remove(i);
                arrays.remove(i);
                arrays.add(i,nums);
                continue;
            }

            i++;
        }

        int[][] res = new int[arrays.size()][2];

        for (int i = 0; i < arrays.size(); i++) {
            res[i] = arrays.get(i);
        }

        return res;
    }


    private void quickSortArrays(List<int[]> arrays,int left,int right){
        if(left >= right)
            return;
        int pos = partitionArray(arrays,left,right);
        quickSortArrays(arrays,left,pos-1);
        quickSortArrays(arrays,pos+1,right);
    }

    private int partitionArray(List<int[]> arrays,int left,int right){
        int low = left;
        int high = right+1;
        int[]  startArray = arrays.get(left);
        while(low<high){
            while(low<right && arrays.get(++low)[0]<=startArray[0]);
            while(high>left && arrays.get(--high)[0]>=startArray[0]);
            if(low<high){
                Collections.swap(arrays,low,high);
            }
        }
        Collections.swap(arrays,left,high);
        return high;
    }