题目链接

力扣56. 合并区间

思路

合并

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

排序

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

代码

java">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);}
}