高端网站设计收费,知乎 网站建设,网站关键词优化培训,关键词优化快速排名给你一个二维整数数组 ranges #xff0c;其中 ranges[i] [starti, endi] 表示 starti 到 endi 之间#xff08;包括二者#xff09;的所有整数都包含在第 i 个区间中。 你需要将 ranges 分成 两个 组#xff08;可以为空#xff09;#xff0c;满足#xff1a; 每个区… 给你一个二维整数数组 ranges 其中 ranges[i] [starti, endi] 表示 starti 到 endi 之间包括二者的所有整数都包含在第 i 个区间中。 你需要将 ranges 分成 两个 组可以为空满足 每个区间只属于一个组。两个有 交集 的区间必须在 同一个 组内。 如果两个区间有至少 一个 公共整数那么这两个区间是 有交集 的。 比方说区间 [1, 3] 和 [2, 5] 有交集因为 2 和 3 在两个区间中都被包含。 请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大将它对 109 7 取余 后返回。 输入ranges [[6,10],[5,15]]
输出2
解释
两个区间有交集所以它们必须在同一个组内。
所以有两种方案
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。 首先初始化m 0; maxR -1。 把区间按照左端点从小到大排序遍历区间同时维护当前合并的最大区间右端点maxR
如果当前区间的左端点l大于maxR,由于我们已经按照左端点排序了那么后面任何区间都不会和之前的区间有交集换句话说产生了一个新的大区间把m1,同时maxR 当前区间右端点r。否则当前区间要合并到大区间内用当前区间右端点r更新maxR的最大值。 class Solution:def countWays(self, ranges: List[List[int]]) - int:ranges.sort(key lambda p: p[0])m, max_r 0, -1for l, r in ranges:if l max_r:m 1max_r max(max_r, r)return pow(2,m,1_000_000_007)
