【贪心算法, 优先队列, 差分数组】将区间分为最少组数【力扣第 310 场周赛】

题目

6178. 将区间分为最少组数

253. 会议室 II

---

给你一个二维整数数组 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

解题

方法一：贪心 优先队列

思路

这题与是贪心算法经典问题：Interval Partitioning，与 【优先队列】会议室 II 相似。

先把区间数组按照区间左端点升序排序。
然后维护一个最小堆(优先队列)，堆顶表示最新分组的最后一个区间的右端点。
遍历区间数组：

• 如果当前遍历到区间的左端点大于堆顶，说明该区间可以直接接在该分组的末尾，把当前堆顶元素出队，然后把该区间的右端点入队，这样就更新了最新分组的最后一个区间。
• 否则说明需要创建一个新分组，那么就不需要出队当前堆顶元素(表示着最新分组)，直接把该区间的右端点入队。

遍历完成后，队种元素的个数就是最少需要划分的组数。
因为只有每次模拟创建新分组的适合栈顶元素都没出队，那么栈里堆积的每一个元素都表示着一个分组(最后一个区间的右端点)。

代码

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        Queue<Integer> priQueue = new PriorityQueue<>();
        for (int[] interval : intervals) {
            if (!priQueue.isEmpty() && interval[0] > priQueue.peek()) priQueue.poll();
            priQueue.offer(interval[1]);
        }
        return priQueue.size();
    }
}

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<int>> pq;
        for (auto& interval : intervals) {
            if (!pq.empty() && interval[0] > pq.top()) pq.pop();
            pq.push(interval[1]);
        }
        return pq.size();
    }
};

方法二：差分数组

思路

统计每个区间的重叠次数，假设重叠次数为 $k$ 那么此区间必然会贡献 $k$ 个分组。具体来说：维护一个长度为 $10^6+1$ 初始值为 $0$ 的数组，把每一个区间中间的数在数组中增加，遍历一遍该数组，其中最大的数就是最少需要划分的组数。

要频繁对数组中某些区间的元素进行操作，适合使用差分数组。

代码

class Solution {
    static final int N = (int) 1e6 + 10;

    public int minGroups(int[][] intervals) {
        int[] diffs = new int[N];
        for (int[] interval : intervals) {
            ++diffs[interval[0]];
            --diffs[interval[1] + 1];
        }
        int height = 0, cnt = 1;
        for (int i = 1; i < N; ++i) {
            height += diffs[i];
            if (height > cnt) cnt = height;
        }
        return cnt;
    }
}

class Solution {
    const int N = 1e6 + 10;

public:
    int minGroups(vector<vector<int>>& intervals) {
        int diffs[N];
        memset(diffs, 0, sizeof(diffs));
        for (auto& interval : intervals) {
            ++diffs[interval[0]];
            --diffs[interval[1] + 1];
        }
        int height = 0, cnt = 1;
        for (int& diff : diffs) {
            height += diff;
            if (height > cnt) cnt = height;
        }
        return cnt;
    }
};