题目描述
给你一个二维整数数组 ranges
,其中 ranges[i] = [, ]
表示 到
之间(包括二者)的所有整数都包含在第
i
个区间中。
你需要将 ranges
分成 两个 组(可以为空),满足:
- 每个区间只属于一个组。
- 两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数,那么这两个区间是 有交集 的。
- 比方说,区间
[1, 3]
和[2, 5]
有交集,因为2
和3
在两个区间中都被包含。
请你返回将 ranges
划分成两个组的 总方案数 。由于答案可能很大,将它对 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] 也有交集,所以它们也必须在同一个组中。 所以总共有 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 <= 10^5
ranges[i].length == 2
0 <= <= <= 10^9
1. 思路
题目要求我们将一组区间分成两组,其中有交集的区间必须在同一组。因此,首先将有交集的区间合并一个集合,集合与集合之间不存在有交集的区间,因此每个集合可以选择分到第一组还是第二组。如果最终得到 k 个集合,那么方案数就是 。
区间合并的思路与「56. 合并区间-CSDN博客」一致,我们首先按照左端点从小到大对区间进行排序,然后对于第 i 个区间,不断地向右扩展与它有交集的区间。令 r=ranges[i][1],r 是当前右端点。过程中还需不断更新右端点,直到下一个区间不再与之相交为止。具体来说,j=i+1,当 j<n,并且 ranges[j][0]≤r 时,就继续合并第 j 个区间,更新 r=max(r,ranges[j][1]),然后令 j 加 1。当条件不满足时,k 增加 1。
2. 代码
class Solution {
static final int MOD = 1000000007;
public int countWays(int[][] ranges) {
Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
int n = ranges.length;
int res = 1;
for (int i = 0; i < n; ) {
int r = ranges[i][1];
int j = i + 1;
while (j < n && ranges[j][0] <= r) {
r = Math.max(r, ranges[j][1]);
j++;
}
res = res * 2 % MOD;
i = j;
}
return res;
}
}