LeetCode 题解工作台
将区间分为最少组数
给你一个二维整数数组 intervals ，其中 intervals[i] = [left i , right i ] 表示 闭 区间 [left i , right i ] 。 你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 …
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们先将区间按左端点排序，用小根堆维护每组的最右端点（堆顶是所有组的最右端点的最小值）。 接下来，我们遍历每个区间：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个二维整数数组 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 <= 105intervals[i].length == 21 <= lefti <= righti <= 106
解题思路
方法一：贪心 + 优先队列（小根堆）
我们先将区间按左端点排序，用小根堆维护每组的最右端点（堆顶是所有组的最右端点的最小值）。
接下来，我们遍历每个区间：
- 若当前区间左端点大于堆顶元素，说明当前区间可以加入到堆顶元素所在的组中，我们直接弹出堆顶元素，然后将当前区间的右端点放入堆中；
- 否则，说明当前没有组能容纳当前区间，那么我们就新建一个组，将当前区间的右端点放入堆中。
时间复杂度 ，空间复杂度 。其中 是数组 intervals 的长度。
class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
q = []
for left, right in sorted(intervals):
if q and q[0] < left:
heappop(q)
heappush(q, right)
return len(q)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N + K) |
| 空间 | O(K) |
面试官常问的追问
外企场景- question_mark
They may hint at using sorting or heap to track overlapping ends.
- question_mark
Expect discussion about greedy assignment of intervals to earliest available groups.
- question_mark
They could ask about handling extreme overlaps or edge intervals in large datasets.
常见陷阱
外企场景- error
Failing to sort intervals correctly can lead to assigning intervals to the wrong group.
- error
Overlooking intervals that start exactly when another ends can inflate group count unnecessarily.
- error
Using nested loops instead of a heap or counter may exceed time limits for large N.
进阶变体
外企场景- arrow_right_alt
Compute maximum number of overlapping intervals at any time, which directly informs group count.
- arrow_right_alt
Return the actual grouping of intervals rather than just the count, using similar scanning logic.
- arrow_right_alt
Handle intervals with additional constraints like weighted priorities or fixed group sizes.