侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-12 / 0 评论 / 0 点赞 / 27 阅读 / 1,005 字 / 正在检测是否收录...

题目

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();
    }
};

方法二:差分数组

思路

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

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

代码

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;
    }
};
0

评论区