题目
给你一个二维整数数组 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();
}
};
方法二:差分数组
思路
统计每个区间的重叠次数,假设重叠次数为 那么此区间必然会贡献 个分组。具体来说:维护一个长度为 初始值为 的数组,把每一个区间中间的数在数组中增加,遍历一遍该数组,其中最大的数就是最少需要划分的组数。
要频繁对数组中某些区间的元素进行操作,适合使用差分数组。
代码
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;
}
};
评论区