2406. 将区间分为最少组数

🟠   🔖  贪心 数组 双指针 前缀和 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].

You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Return theminimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.

Example 1:

Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]

Output: 3

Explanation: We can divide the intervals into the following groups:

• Group 1: [1, 5], [6, 8].
• Group 2: [2, 3], [5, 10].
• Group 3: [1, 10].

It can be proven that it is not possible to divide the intervals into fewer than 3 groups.

Example 2:

Input: intervals = [[1,3],[5,6],[8,10],[11,13]]

Output: 1

Explanation: None of the intervals overlap, so we can put all of them in one group.

Constraints:

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

题目大意

给你一个二维整数数组 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

解题思路

这道题考察了如何有效地处理区间重叠问题，属于典型的 区间调度问题，可以将这个问题转换为求区间的最大重叠数。

1. 将每个区间的起始时间和结束时间拆分成两个事件。将每个起始事件记录为正值，结束事件记录为负值。

   • 当遇到一个开始事件时，意味着需要新增一个组（可以理解为需要新的资源，如椅子、会议室等）；
   • 当遇到一个结束事件时，意味着可以释放一个资源；

2. 将这些事件按照时间从小到大排序，如果时间相同，则开始事件（正值）优先于结束事件（负值）。

3. 遍历所有的事件，维护当前进行中的区间数，并记录下最大同时进行的区间数，这个数即为需要的最少组数。

复杂度分析

• 时间复杂度：O(n log n)，因为需要对事件数组进行排序，n 是区间的数量。
• 空间复杂度：O(n)，用于存储所有的事件。

代码

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minGroups = function (intervals) {
	let events = [];

	// 把每个区间的起始时间和结束时间作为事件存储
	for (let [left, right] of intervals) {
		events.push([left, 1]); // 1 表示开始
		events.push([right, -1]); // -1 表示结束
	}

	// 按照时间排序，如果时间相同，先处理开始事件
	events.sort((a, b) => (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));

	let cur = 0,
		max = 0;

	// 遍历所有事件，计算最大重叠数
	for (let [time, type] of events) {
		if (type == 1) {
			cur++;
		} else {
			cur--;
		}
		max = Math.max(max, cur);
	}
	return max;
};

相关题目

题号	标题	题解	标签	难度
56	合并区间	[✓]	数组 排序
1419	数青蛙	[✓]	字符串 计数
2015	每段建筑物的平均高度 🔒		贪心 数组 排序 1+