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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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

本题和 56. 合并区间 是类似的。

我们需要把有交集的区间都归在同一个集合中，假设最后分成了 m 个集合，那么每个集合都可以决定要在第一个组还是第二个组，所以方案数为 2^m。

怎么求出 m 呢？

初始化 m=1。按照左端点排序，遍历数组，同时维护区间右端点的最大值 maxR：

  • 如果当前区间的左端点大于 maxR，由于已经按照左端点排序了，那么后面任何区间都不会和之前的区间有交集，换句话说，产生了一个新的集合，m 加一。
  • 否则，当前区间与上一个区间在同一个集合。

附：视频讲解

[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort(key=lambda p: p[0])
        m, max_r = 1, ranges[0][1]
        for l, r in ranges:
            m += l > max_r  # 产生了一个新的集合
            max_r = max(max_r, r)
        return pow(2, m, 10 ** 9 + 7)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countWays(int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
        int ans = 2, maxR = ranges[0][1];
        for (var p : ranges) {
            if (p[0] > maxR) // 产生了一个新的集合
                ans = ans * 2 % MOD;
            maxR = Math.max(maxR, p[1]);
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    const int MOD = 1e9 + 7;
public:
    int countWays(vector<vector<int>> &ranges) {
        sort(ranges.begin(), ranges.end(), [](auto &a, auto &b) {
            return a[0] < b[0];
        });
        int ans = 2, max_r = ranges[0][1];
        for (auto &p : ranges) {
            if (p[0] > max_r) // 产生了一个新的集合
                ans = ans * 2 % MOD;
            max_r = max(max_r, p[1]);
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func countWays(ranges [][]int) int {
	const mod int = 1e9 + 7
	sort.Slice(ranges, func(i, j int) bool { return ranges[i][0] < ranges[j][0] })
	ans, maxR := 2, ranges[0][1]
	for _, p := range ranges[1:] {
		if p[0] > maxR { // 产生了一个新的集合
			ans = ans * 2 % mod
		}
		maxR = max(maxR, p[1])
	}
	return ans
}

func max(a, b int) int { if a < b { return b }; return a }

复杂度分析

  • 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)。忽略排序时的栈开销，仅用到若干额外变量。

相似题目

 Comments
On this page
2580-统计将重叠区间合并成组的方案数
  1. 复杂度分析
  2. 相似题目