合并区间

以数组 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，如果返回正数，两个数交换，如果返回负数两个数位置不变

      a-b是升序（小根堆），b-a是倒序（大根堆）

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
class MedianFinder {
    Queue<Integer> left;
    Queue<Integer> right;

    public MedianFinder() {
        left = new PriorityQueue<>((a, b) -> b - a);
        right = new PriorityQueue<>((a, b) -> a - b);
    }

    public void addNum(int num) {
        // 要让left的个数=right的个数
        // 或者left的个数比right多1

        // 如果相等，就加入left
        // 需要先加入右边，然后把右边最小值给左边
        if (left.size() == right.size()) {
            right.offer(num);
            left.offer(right.poll());
        } else { // 如果不相等，说明左边多一，就加入右边
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        } else {
            return left.peek();
        }
    }
}