将区间分为最少组数

标签: 贪心 数组 双指针 前缀和 排序 堆（优先队列）

难度: Medium

给你一个二维整数数组 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 <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 106

Submission

运行时间: 216 ms

内存: 43.6 MB

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        h = []
        for start, end in intervals:
            if h and start > h[0]:
                heapreplace(h, end)
            else:
                heappush(h, end)
        return len(h)

Explain

本题解的思路是利用贪心算法和最小堆（优先队列）来求解。首先，将所有区间按照起始位置进行排序。排序之后，遍历每个区间，并使用一个最小堆来维护当前活跃的区间组的结束时间。对于每个区间，如果它的起始时间大于堆顶的区间结束时间（表示该区间可以加入到当前最早结束的区间组中），则用当前区间的结束时间替换堆顶元素（更新该组的结束时间）。如果不满足上述条件（表示当前区间与所有活跃组都有重叠），则新开一个区间组，并将当前区间的结束时间加入堆中。最终，堆的大小即为所需的最少区间组数。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])  # 按起始时间排序区间
        h = []  # 最小堆，存储活跃区间组的结束时间
        for start, end in intervals:  # 遍历每个区间
            if h and start > h[0]:  # 如果当前区间可以加入最早结束的区间组
                heapreplace(h, end)  # 更新该组的结束时间
            else:
                heappush(h, end)  # 否则新建一个区间组
        return len(h)  # 堆的大小即为所需的最少区间组数

Explore

当当前区间的起始时间小于或等于最小堆（优先队列）中的堆顶元素时，即当前区间的起始时间小于或等于所有活跃区间组中最早结束的区间组的结束时间时，说明当前区间与所有已有的区间组都至少有一个共同点或重叠部分，因此无法加入任何一个已有的区间组。在这种情况下，必须新开一个区间组，并将当前区间的结束时间加入到最小堆中。