力扣56. 合并区间

题目链接

力扣56. 合并区间

思路

合并

先对每个区间进行排序，左端点值小的放在前面。然后对这些区间进行合并，对于一个的结果集合，如果本区间与前一个区间不重叠，则创建一个新区间加入到这个集合中；否则取这两个区间右端点的最大值作为前一个区间的右端点，这就是合并两个区间为一个区间的操作。

排序

对于 $Java$ 来说，可以使用 $Math.sort()$ 方法进行排序，即有 Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);，此处使用了 $lambda$ 表达式简化内部类的编写。
但是这样的性能不是很高，执行时间大约为 $7ms$，可以自己实现一个排序的方法，本题采用定制快速排序的方法进行排序，如果对快速排序不了解，可以先看看这篇文章快速排序。

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        // 1. 如果intervals为空，则返回空数组
        if (intervals.length == 0) {
            return new int[0][2];
        }

        // 2. 按区间左端点的大小进行排序
        quickSort(intervals, 0, intervals.length - 1);

        // 3. 对区间进行合并
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0];             // 本轮循环的区间左端点
            int right = intervals[i][1];            // 本轮循环的区间右端点

            if (res.size() == 0) {                  // 若res为空 
                res.add(new int[]{left, right});    // 增加一个新的区间
                continue;                           // 不必进行区间的比较
            }

            int[] tmp = res.get(res.size() - 1);
            if (tmp[1] < left) {                    // 若两个区间不重叠
                res.add(new int[]{left, right});    // 增加一个新的区间
            } else {                                // 否则
                tmp[1] = Math.max(tmp[1], right);   // 让区间的右端点取 原右端点 和 现右端点 的最大值
            }
        }

        // 4. 返回一个二维数组
        return res.toArray(new int[res.size()][]);
    }

    private void quickSort(int[][] intervals, int left, int right) {
        if (left > right) {
            return;
        }

        int tmp = intervals[left][0]; // 默认以数组的左端点作为基准进行排序
        int[] t;
        int i = left;
        int j = right;

        // 分区
        while (i < j) {
            // 获取大于tmp的元素的索引
            while (tmp <= intervals[j][0] && i < j) {
                j--;
            }

            // 获取小于tmp的元素的索引
            while (tmp >= intervals[i][0] && i < j) {
                i++;
            }

            // 将小于tmp的元素放在左边，将大于tmp的元素放在右边
            t = intervals[j];
            intervals[j] = intervals[i];
            intervals[i] = t;
        }

        // i指向小于tmp的最后一个元素，将基准放到小于tmp和大于tmp的中间
        int[] arr = intervals[left];
        intervals[left] = intervals[i];
        intervals[i] = arr;

        // 对tmp左边进行分区
        quickSort(intervals, left, j - 1);
        // 对tmp右边进行分区
        quickSort(intervals, j + 1, right);
    }
}