统计将重叠区间合并成组的方案数

标签: 数组 排序

难度: Medium

给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组（可以为空），满足：

  • 每个区间只属于一个组。
  • 两个有 交集 的区间必须在 同一个 组内。

如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。

  • 比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。

请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。

示例 1：

输入：ranges = [[6,10],[5,15]]
输出：2
解释：
两个区间有交集，所以它们必须在同一个组内。
所以有两种方案：
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。

示例 2：

输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
输出：4
解释：
区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
所以总共有 4 种分组方案：
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。

提示：

  • 1 <= ranges.length <= 105
  • ranges[i].length == 2
  • 0 <= starti <= endi <= 109

Submission

运行时间: 75 ms

内存: 44.0 MB

MOD = 1_000_000_007
class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort(key=lambda x: x[0])
        n, bound = 0, -1
        for l, r in ranges:
            if l > bound: n += 1
            if r > bound: bound = r
        return pow(2, n, MOD)

Explain

题解中采用了图的连通分量的思想。首先，通过对区间按照起始点进行排序，确保处理顺序的逻辑性。在遍历排序后的区间时，用一个变量bound来维持当前已遍历区间的最大结束点。如果当前区间的起始点大于bound，说明此区间与之前的区间不连续，即形成了一个新的连通分量。变量n记录这样的连通分量的数量。每一个连通分量都可以独立选择放在两个不同的组中，因此最终的方案数是2的n次幂，使用pow函数可以高效地计算模1_000_000_007下的结果。

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

空间复杂度: O(1)

MOD = 1_000_000_007

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort(key=lambda x: x[0])  # 按区间起始点排序
        n, bound = 0, -1  # n记录连通分量的数量，bound记录当前连通分量的最大结束点
        for l, r in ranges:  # 遍历所有区间
            if l > bound:  # 如果当前区间的起始点大于bound，形成新的连通分量
                n += 1  # 连通分量数增加
            if r > bound:  # 更新当前连通分量的最大结束点
                bound = r
        return pow(2, n, MOD)  # 返回2的n次幂模1_000_000_007的结果

Explore

在题解中，通过将区间按照其起始点进行排序，确保了我们在处理它们的时候遵循时间序。这允许我们顺序检查每个区间与前一个区间是否存在重叠或连续性。使用一个变量`bound`来记录当前连通分量的最大结束点，每次遇到一个新区间，我们会检查这个区间的起始点是否大于`bound`。如果是，这意味着当前区间无法与先前的区间连续，从而标志着一个新的连通分量的开始。这个方法通过顺序遍历和比较，能够准确地辨别并计算所有连通分量的数量。

当我们确定一个区间的起始点大于之前所有区间的最大结束点`bound`时，这个区间显然与之前的区间不再连续，因此它必然开始了一个新的连通分量。这个逻辑的正确性基于我们已经按照起始点排序的前提。因此，每次这种情况发生时，我们可以确信一个新的连通分量已经开始，无需进行额外的检查或验证。

是的，这个逻辑完全基于区间列表已经根据起始点进行了排序的假设。如果区间没有被完全排序，那么我们可能无法正确识别新的连通分量。例如，如果一个较早开始的区间在排序后的位置较晚，这可能导致我们错误地将其视为新的连通分量，从而错误地计算连通分量的总数。因此，排序是识别连通分量的关键步骤，对于算法的正确性至关重要。

这种更新策略确实考虑了所有可能的情况，包括新区间完全被前一个区间包含的情况。在这种情况下，新区间的结束点`r`不会大于当前的`bound`，因此`bound`不需要更新。这是因为`bound`始终表示当前连通分量中所有区间的最大结束点，无论这些区间的相对包含关系如何。只有当一个区间有更远的结束点时，我们才需要更新`bound`，以保证它覆盖所有相关的区间。