2406-将区间分为最少组数

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

本题 视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

按照 left 排序后，用最小堆模拟，堆顶存储每个组最后一个区间的 right。

遍历区间：

• 如果当前的 left 大于堆顶，则可以接在这个组的末尾，更新堆顶为 right；
• 否则需要创建一个新的组。

[sol1-Python3]

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

[sol1-Java]

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        var pq = new PriorityQueue<Integer>();
        for (var p : intervals) {
            if (!pq.isEmpty() && pq.peek() < p[0]) pq.poll();
            pq.offer(p[1]);
        }
        return pq.size();
    }
}

[sol1-C++]

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<>> pq;
        for (auto &p : intervals) {
            if (!pq.empty() && pq.top() < p[0]) pq.pop();
            pq.push(p[1]);
        }
        return pq.size();
    }
};

[sol1-Go]

func minGroups(intervals [][]int) int {
	h := hp{}
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	for _, p := range intervals {
		if h.Len() == 0 || p[0] <= h.IntSlice[0] {
			heap.Push(&h, p[1])
		} else {
			h.IntSlice[0] = p[1]
			heap.Fix(&h, 0)
		}
	}
	return h.Len()
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

另外一种思路是转换成上下车模型，每个区间看成一个人，他在 left 时刻上车，right}+1 时刻下车，最后答案为同时在车上的人数的最大值。

这可以用差分数组实现，下面代码用的平衡树，方便从小到大计算。

[sol2-C++]

class Solution {
public:
    int minGroups(vector<vector<int>> &intervals) {
        map<int, int> diff;
        for (auto &p : intervals)
            ++diff[p[0]], --diff[p[1] + 1];
        int ans = 0, sum = 0;
        for (auto &[_, d] : diff)
            ans = max(ans, sum += d);
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(n)。

思考题

从所有满足 1\le\textit{left}\le\textit{right}\le m 的一共 \dfrac{m(m+1)}{2 个区间中，随机选择 n 个区间作为本题的输入，得到的答案的期望是多少？