2580. 统计将重叠区间合并成组的方案数
题目描述:
给你一个二维整数数组 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
思路:
这是一道合并区间的题目,首先按照ranges数组的第一个数字,也就是区间的左端点进行排序
遍历排序后数组,维护两个数字,当前大区间的右端点max_r和区间数i
遍历时,当左端点大于当前右端点时,i+1;无论是否出现新的区间,都对区间右侧的maxr进行维护,保存为当前区间与maxr的最大值
代码:
class Solution:
def countWays(self, ranges: List[List[int]]) -> int:
sor_rule = lambda x:x[0]
new = sorted(ranges,key=sor_rule)
max_r = -1
i=0
for left,right in new:#待比对项
#通过遍历,合并有交集的集合,计算无交集的集合数n
if left >max_r :
new[i][1]=right
i+=1
max_r=max(right,max_r)
return pow(2,i,1000000007)