【2024.03.27】LeetCode每日一题·统计将重叠区间合并成组的方案数

2024年03月27日 21时56分

标签： LeetCode 数组二分数学双指针

## 题目描述

给你一个二维整数数组`ranges`，其中`ranges[i] = [start_i, end_i]`表示 `start_i`到`end_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 <= start_i <= end_i <= 10^9
````

#### 来源

> 来源：力扣（LeetCode）
> 
> 链接：https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/description/

## 解题思路

将所有有重叠的区间合并后，记剩下的不重叠的区间的数量为$$n$$，那么最终的答案为

$$C_n^0+C_n^1+\cdots+C_n^n=2^n$$

因此，主要任务在进行区间合并。对此，可以将`ranges`数组按照起始位置排序，然后依次判断当前区间的左端点是否包含在最靠近左端点的range中即可。对于寻找最靠近左端点的range，可以使用二分实现。

时间复杂度：$$O(n\log n)$$

## 代码

````python
class Solution:
    def binary_search(self, arr, value):
        # find the last location in arr which is <= value
        l, r = 0, len(arr) - 1
        while l <= r:
            mid = (r - l) // 2 + l
            if arr[mid] <= value:
                l = mid + 1
            else:
                r = mid - 1

return r
            
    def countWays(self, ranges: List[List[int]]) -> int:
        MOD = 1e9 + 7
        ranges = sorted(ranges, key=lambda x: x[0])

l, r = [], []
        for rng in ranges:
            f, t = rng
            if len(l) == 0:
                l.append(f)
                r.append(t)
            else:
                loc = self.binary_search(l, f) # l[loc]: the range whose begin is <= f, the range is [l[loc], r[loc]]
                if f <= r[loc]: # current range's beginning is inside the selected range
                    r[loc] = max(r[loc], t) # merge the range
                else:
                    # new range
                    l.append(f)
                    r.append(t)

# final result is 2^len(l)
        res = 1
        for i in range(len(l)):
            res = int((res * 2) % MOD)
        return res
````

## 用时和内存
> 执行用时：318 ms，在所有Python提交中击败了5.26%的用户
>
> 内存消耗：45.08 MB，在所有Python提交中击败43.42%的用户
>

## 注
上述方法中，由于如果一个不重叠的数组出现了需要将其`append`到`l`和`r`中，因此时间开销较大。其实可以直接采用双指针（如[区间排序](https://leetcode.cn/problems/merge-intervals/solutions/203562/he-bing-qu-jian-by-leetcode-solution/)）的做法，就可以获得更小的时间复杂度常数和更小的空间复杂度。

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2024.03.27】LeetCode每日一题·统计将重叠区间合并成组的方案数

所有评论

暂无评论

新增评论