class Solution {
public:
int countWays(vector<vector<int>>& ranges) {
}
};
6313. 统计将重叠区间合并成组的方案数
给你一个二维整数数组 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 <= 105ranges[i].length == 20 <= starti <= endi <= 109原站题解
javascript 解法, 执行用时: 119 ms, 内存消耗: 76 MB, 提交时间: 2024-03-27 15:03:42
/**
* @param {number[][]} ranges
* @return {number}
*/
var countWays = function(ranges) {
ranges.sort((a, b) => a[0] - b[0]);
let ans = 1, maxR = -1;
for (const [l, r] of ranges) {
if (l > maxR) { // 无法合并
ans = ans * 2 % 1_000_000_007; // 新区间
}
maxR = Math.max(maxR, r); // 合并
}
return ans;
};
rust 解法, 执行用时: 20 ms, 内存消耗: 9.5 MB, 提交时间: 2024-03-27 15:03:26
impl Solution {
pub fn count_ways(mut ranges: Vec<Vec<i32>>) -> i32 {
ranges.sort_unstable_by(|a, b| a[0].cmp(&b[0]));
let mut ans = 1;
let mut max_r = -1;
for p in &ranges {
if p[0] > max_r { // 无法合并
ans = ans * 2 % 1_000_000_007; // 新区间
}
max_r = max_r.max(p[1]); // 合并
}
ans
}
}
cpp 解法, 执行用时: 248 ms, 内存消耗: 71 MB, 提交时间: 2023-04-02 12:31:35
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;
}
};
golang 解法, 执行用时: 160 ms, 内存消耗: 19.6 MB, 提交时间: 2023-04-02 12:31:21
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 }
java 解法, 执行用时: 14 ms, 内存消耗: 98.5 MB, 提交时间: 2023-04-02 12:31:10
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;
}
}
python3 解法, 执行用时: 96 ms, 内存消耗: 42.2 MB, 提交时间: 2023-04-02 12:30:59
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)