【LeetCode】310c：将区间分为最少组数

原题链接： 310c：将区间分为最少组数

题目大意

给你一个二维整数数组 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 个组。
1
2
3
4
5
6
7

示例 2：

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

提示：

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

思路

贪心。首先对所有的区间按照左端点进行从小到大排序，然后遍历。
通过一个小根堆存储每个分组的代表区间的右端点。对于当前区间r，若其左端点小于等于最小的右端点，则说明其与所有分组都有重叠(因为已经按照左端点排序过，则当前区间的左端点大于等于先前区间的左端点)，因此将其压入堆，形成新的一组。
否则，若当前区间左端点大于堆顶区间的右端点，则不用增加组数，只需要更新该组的右端点，即将堆顶弹出再压入该组修正后的右端点。
最终返回的堆的大小即为答案。

代码

class Solution {
public:
    int minGroups(vector<vector<int>>& inters) {
        int n = inters.size();
        sort(inters.begin(), inters.end());
        priority_queue<int, vector<int>, greater<int>> heap;
        for(int i = 0; i < n; i ++ )
        {
            auto r = inters[i];
            if(heap.empty() || heap.top() >= r[0]) heap.push(r[1]);
            else
            {
                heap.pop();
                heap.push(r[1]);
            }
        }
        
        return heap.size();
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度

$O(nlogn)$ 遍历n个区间时，每个区间涉及到堆的push等操作的复杂度为log级别。