Medium

题目描述

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

你需要将 ranges 分割成两个（可能为空的）组，使得：

  • 每个区间恰好属于一个组。
  • 任意两个重叠的区间必须属于同一个组。

如果两个区间至少有一个整数相同，则称它们重叠。

  • 例如，[1, 3] 和 [2, 5] 重叠，因为 2 和 3 同时出现在两个区间中。

返回将区间分割成两个组的总方法数。由于答案可能很大，请返回对 10^9 + 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] 也重叠。所以它们也必须在同一个组中。
因此，有四种可能的分组方法：
- 所有区间都在组 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 <= 10^5
  • ranges[i].length == 2
  • 0 <= starti <= endi <= 10^9

解题思路

这道题的核心思想是通过合并重叠区间来找出独立的连通组件，然后计算分组方法数。

解题思路：

  1. 区间合并：首先对所有区间按起始位置排序，然后合并所有重叠的区间。重叠的区间必须在同一组中，所以我们需要将它们看作一个整体。

  2. 连通组件计数：合并后得到的每个独立区间代表一个连通组件。由于重叠的区间已经合并，剩下的区间之间互不影响。

  3. 分组方案计算：对于 n 个独立的连通组件，每个组件都有两种选择：放入组1或组2。因此总的分组方法数为 2^n。

算法步骤：

  • 对区间按起始位置排序
  • 遍历排序后的区间，合并重叠区间
  • 统计合并后的独立区间数量
  • 返回 2^(独立区间数) 对 10^9 + 7 的模

时间复杂度分析： 主要是排序的 O(n log n)，其中 n 是区间数量。 空间复杂度分析： O(1)，只使用常数额外空间。

代码实现

class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        const int MOD = 1e9 + 7;
        
        // 按起始位置排序
        sort(ranges.begin(), ranges.end());
        
        int groups = 1; // 至少有一个组
        int currentEnd = ranges[0][1];
        
        // 合并重叠区间，统计独立组数
        for (int i = 1; i < ranges.size(); i++) {
            if (ranges[i][0] > currentEnd) {
                // 当前区间与之前区间不重叠，形成新组
                groups++;
                currentEnd = ranges[i][1];
            } else {
                // 重叠，更新当前组的结束位置
                currentEnd = max(currentEnd, ranges[i][1]);
            }
        }
        
        // 计算2^groups % MOD
        long long result = 1;
        for (int i = 0; i < groups; i++) {
            result = (result * 2) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # 按起始位置排序
        ranges.sort()
        
        groups = 1  # 至少有一个组
        current_end = ranges[0][1]
        
        # 合并重叠区间，统计独立组数
        for i in range(1, len(ranges)):
            if ranges[i][0] > current_end:
                # 当前区间与之前区间不重叠，形成新组
                groups += 1
                current_end = ranges[i][1]
            else:
                # 重叠，更新当前组的结束位置
                current_end = max(current_end, ranges[i][1])
        
        # 计算2^groups % MOD
        return pow(2, groups, MOD)

public class Solution {
    public int CountWays(int[][] ranges) {
        const int MOD = 1000000007;
        
        // 按起始位置排序
        Array.Sort(ranges, (a, b) => a[0].CompareTo(b[0]));
        
        int groups = 1; // 至少有一个组
        int currentEnd = ranges[0][1];
        
        // 合并重叠区间，统计独立组数
        for (int i = 1; i < ranges.Length; i++) {
            if (ranges[i][0] > currentEnd) {
                // 当前区间与之前区间不重叠，形成新组
                groups++;
                currentEnd = ranges[i][1];
            } else {
                // 重叠，更新当前组的结束位置
                currentEnd = Math.Max(currentEnd, ranges[i][1]);
            }
        }
        
        // 计算2^groups % MOD
        long result = 1;
        for (int i = 0; i < groups; i++) {
            result = (result * 2) % MOD;
        }
        
        return (int)result;
    }
}

var countWays = function(ranges) {
    const MOD = 1e9 + 7;
    
    // 按起始位置排序
    ranges.sort((a, b) => a[0] - b[0]);
    
    let groups = 1; // 至少有一个组
    let currentEnd = ranges[0][1];
    
    // 合并重叠区间，统计独立组数
    for (let i = 1; i < ranges.length; i++) {
        if (ranges[i][0] > currentEnd) {
            // 当前区间与之前区间不重叠，形成新组
            groups++;
            currentEnd = ranges[i][1];
        } else {
            // 重叠，更新当前组的结束位置
            currentEnd = Math.max(currentEnd, ranges[i][1]);
        }
    }
    
    // 计算2^groups % MOD
    let result = 1;
    for (let i = 0; i < groups; i++) {
        result = (result * 2) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要是排序操作的时间复杂度
空间复杂度O(1)只使用常数额外空间

相关题目