周赛：将区间分为最少组数

646. 最长数对链

6178. 将区间分为最少组数

本次周赛的第三题 将区间分为最少组数 和某一天的每日一题 最长数对链 很像！！

这里给出三种思路：「贪心 + 堆」「线段树」「差分数组」

贪心 + 堆

首先排个序：先按照left排序，如果相同，再按right排序

堆中存放着每一个分组中结尾元素值，即分组的最大元素值

• 如果当前区间的左边界 <= 堆顶元素，说明所有分组结尾值均 >= 当前区间的左边界，只能新创一个分组
• 如果当前区间的左边界 > 堆顶元素，说明可以接在堆顶元素后面。也可以接在其他比左边界小的元素后面，其效果都是一样的，因为数组是按照left排序，当前区间可以接的元素，那么后续区间也一定可以接

对于上述第二种情况，举个简单的例子

假设当前堆中元素为：2 5 8 15，其中 2 为堆顶，此时要加入区间[10, 20]，可以接在 2 后面，也可以接在 5 或 8 后面，效果都是等价的

如果接在 5 后面，后续区间左边界一定 >= 10，所以后续区间一定可以接在 2 或 8 后面

为了方便处理，每次都接在堆顶元素后面即可！！

public int minGroups(int[][] intervals) {
    // 最小堆
    Queue<Integer> pq = new PriorityQueue<>();
    // 排序
    Arrays.sort(intervals, (a, b) -> {
        if (a[0] != b[0]) return a[0] - b[0];
        else return a[1] - b[1];
    });
    for (int[] cur : intervals) {
        int left = cur[0], right = cur[1];
        // 如果堆为空，直接加入堆中
        if (pq.isEmpty()) pq.offer(right);
        else {
            // left <= pq.peek() 表示当前区间无法接在任何一个分组后面，只能新创一个分组
            if (left <= pq.peek()) pq.offer(right);
            else {
                // 表示当前区间可以接在最小分组后面
                pq.poll();
                pq.offer(right);
            }
        }
    }
    return pq.size();
}

线段树

关于线段树的详解可见 线段树详解 🔥🔥🔥

如果使用线段树去解决，可以直接套模版，详解中有详细说明！！这里是关于「区间最值」的线段树类型

本题直接转换成计算区间重叠的最大高度，如下图所示高度为 3：

xxxxxxxxxx
class Solution {
    public int minGroups(int[][] intervals) {
        for (int[] cur : intervals) {
            update(root, 1, N, cur[0], cur[1], 1);
        }
        // 根节点表示整个区间的最值
        return root.val;
    }
    // ---------- 以下是模版 ----------
    class Node {
        Node left, right;
        int val, add;
    }
    private int N = (int) 1e6;
    private Node root = new Node();
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val += val;
            node.add += val;
            return ;
        }
        pushDown(node);
        int mid = (start + end) >> 1;
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        pushDown(node);
        int mid = (start + end) >> 1, ans = 0;
        if (l <= mid) ans = query(node.left, start, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
        return ans;
    }
    private void pushUp(Node node) {
        // 更新区间最值
        node.val = Math.max(node.left.val, node.right.val);
    }
    private void pushDown(Node node) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val += node.add;
        node.right.val += node.add;
        // 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}

差分数组

关于差分数组的详解可见 差分数组 🔥🔥🔥

在前一种线段树方法中，直接转换成计算区间重叠的最大高度，那么我们也可以利用「差分数组」计算出每个区间的重叠高度

xxxxxxxxxx
public int minGroups(int[][] intervals) {
    int max = intervals[0][1];
    for (int[] interval : intervals) {
        max = Math.max(max, interval[1]);
    }
    int[] diff = new int[max + 1];
    for (int[] interval : intervals) {
        diff[interval[0]] += 1;
        if (interval[1] + 1 <= max) {
            diff[interval[1] + 1] -= 1;
        }
    }
    int t = 0, ans = 0;
    for (int i = 1; i <= max; i++) {
        t = t + diff[i];
        ans = Math.max(ans, t);
    }
    return ans;
}