leet2406. 将区间分为最少组数

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

示例 1：

输入： intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]] 输出： 3 解释： 我们可以将区间划分为如下的区间组：

• 第 1 组：[1, 5] ，[6, 8] 。
• 第 2 组：[2, 3] ，[5, 10] 。
• 第 3 组：[1, 10] 。 可以证明无法将区间划分为少于 3 个组。

示例 2：

输入： intervals = [[1,3],[5,6],[8,10],[11,13]] 输出： 1 解释： 所有区间互不相交，所以我们可以把它们全部放在一个组内。

提示：

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• 1 <= lefti <= righti <= 10^6

---

谁懂啊，刷堆的题单刷到这题。完全不知道用堆怎么做，一翻评论竟然还可以用差分数组！

思路一（差分数组）

按照题目提示（我是没想到），划分为多少组等价于找到所有区间重叠次数最多的那个点。例如示例1，在 x = 5 这个地方有三个区间重叠：

• 【1，5】
• 【5，10】
• 【1，10】

因此，至少需要3个分组才能保证组内没有重叠。所以原问题等价于找到一个点，或一个范围，在这个范围内所有区间中有 k 个在次重叠。那么至少就要划分 k 组，k 就是答案。

按左端点从小到大的顺序遍历所有区间，将区间内的计数+1，最后统计最大的计数即可。

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        map<int,int> diff;
        for (auto& i : intervals) {
            int left = i[0], right = i[1];
            diff[left]++; // 插入时自动排序
            diff[right+1]--; // 维护差分数组边界
        } 
        int ans = 0;
        int psum = 0; // 记录前缀和
        for (auto& m : diff) {
            psum += m.second;
            ans = max(ans, psum);
        }
        return ans;
    }
};

思路二（小顶堆）

按照区间左端点 left 进行排序。遍历所有区间，每个区间的右端点 right 入堆。

• 当前 left 大于堆顶，表明当前区间可以和上一个分在一组（不重叠）
• 否则需要创建一个新组

参考：https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/solutions/1816294/by-endlesscheng-ze3t

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });
        priority_queue<int, vector<int>, greater<>> min_heap;
        for (auto& i : intervals) {
            int left = i[0], right = i[1];
            if (!min_heap.empty() && left > min_heap.top()) {
                min_heap.pop();
            }
            min_heap.push(right);
        }
        return min_heap.size();
    }
};