题目 #
给你一个二维整数数组 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
解法 #
其实是一道简单的数理统计题。
我们可以在排序之后遍历 ranges, 找到重叠的区间，由于重叠的区间只能分在同一个 group, 所以我们索性将它们合并为一个区间。完成所有的合并之后，我们就得到了一些互相独立的区间，它们可以互不影响的分配在任意一个 group 当中，设合并后的区间数为 rCount, 则最终答案为 2^rCount.
代码 #
class Solution:
def countWays(self, ranges: List[List[int]]) -> int:
ranges.sort()
rCount = 0
preEnd = -1
for [start, end] in ranges:
if start > preEnd:
rCount += 1
preEnd = end
else:
preEnd = max(preEnd, end)
return (2 ** rCount) % (10 ** 9 + 7)