56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

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

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

要注意到二维数组的排序这个问题，通过修改compare迭代器

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[][] merge(int[][] intervals) {
        int i = 0;  // i是当前区间的索引
        int j = 1;  // j是下一个区间的索引
        int[][] ans = new int[intervals.length][2]; // 创建结果数组，最大可能的长度与输入相同
        int cnt = 0; // 用于计数合并后的区间数量

        // 对区间按照每个区间的起始位置进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
       
        while (j <= intervals.length) { // 遍历区间，直到j超出数组长度
            while (j < intervals.length && intervals[i][1] >= intervals[j][0]) {
                // 当下一个区间的开始小于或等于当前区间的结束时，说明有重叠
                if (intervals[j][1] >= intervals[i][1]) {
                    // 如果下一个区间的结束大于当前区间的结束，扩展当前区间
                    intervals[i][1] = intervals[j][1];
                    j++;
                } else {
                    // 如果下一个区间完全包含在当前区间内，只需移动j
                    j++;                   
                }
            }
       
            // 将当前不再有重叠的区间添加到结果数组
            ans[cnt++] = intervals[i];
            i = j; // 移动i到j，j为下一个待检查的区间
            j++;   // j移动到下一个区间
        }

        // 根据合并后实际的区间数量调整返回数组的大小
        int[][] x = new int[cnt][2];
        for (int k = 0; k < cnt; k++) {
            x[k] = ans[k]; // 将结果复制到新的大小合适的数组
        }
        return x; // 返回合并后的区间数组
    }
}