23 问题转化

2406. 将区间分为最少组数

前言

「算法题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 23 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🟡中等

标签：#贪心数组双指针前缀和排序堆

给你一个二维整数数组 intervals，其中 intervals[i] = [l_i, r_i] 表示 闭 区间 [l_i, r_i] 。

你需要将 intervals 划分为一个或者多个区间 组，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

输入: 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 个组

解题思路

问题转化：有重叠的区间不能在一组，转化为计算有多少区间存在重叠。

按左端点排序，用堆维护每组最后一个区间的右端点，遍历 intervals：

• 如果 l_i > 堆顶：无重叠，修改 堆顶为当前区间的末端 r_i（相当于扩充了上个区间）。
• 如果 l_i <= 堆顶 ：有重叠，需要新分出一组，更新 堆顶为 r_i。

遍历结束后堆的大小即为答案。

复杂度

• 时间复杂度：$O(N\log N)$，来自排序
• 空间复杂度：$O(N)$

代码

Java

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

最后

更多系列「外源推文」&「生活分享」关注公众号：