合并区间

以数组 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] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

解析点这

重点讲一下java的自定义排序

Comparator 的工作原理

  1. 接口定义： Comparator 接口定义了以下两个方法：

    1
    2
    javaCopyEditint compare(T o1, T o2);
    boolean equals(Object obj);

    • compare(T o1, T o2)：该方法用来比较两个对象 o1 和 o2。它返回一个整数，表示 o1 和 o2 的排序顺序：

      • 如果返回负数 (< 0)，表示 o1 排在 o2 前面；
      • 如果返回正数 (> 0)，表示 o1 排在 o2 后面；
      • 如果返回 0，表示 o1 和 o2 相等。

      参数o1的下标小于参数o2，如果返回正数，两个数交换，如果返回负数两个数位置不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 0; i < intervals.length; i++) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            if (end >= l && end < r) {
                end = r;
            } else if (end < l) {
                res.add(new int[] { start, end });
                start = l;
                end = r;
            }
        }
        res.add(new int[] { start, end });
        return res.toArray(new int[res.size()][]);
    }
}