2580.统计将重叠区间合并成组的方案数

【LetMeFly】2580.统计将重叠区间合并成组的方案数：排序（几行代码解决）——一步步思路描述版

力扣题目链接：https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/

给你一个二维整数数组 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

方法一：排序

思路

解决这道题需要明白以下两点：

1. $n$个区间分成两组，有多少种分法。
2. 合并所有有交集的区间后，还剩多少个区间（并将其记为$n$）。

方法

$n$个区间分成两组，有多少种分法：

根据示例1，一个区间分到2组，有两种分法。也就是说两个小组不同，[1]、[]和[]、[1]是两种不同的分法。

因此我们只需要从$n$个区间中取$k$个放到第一组，剩下的放到第二组中即可（$1\leq k\leq n$）。每个区间都可以被取和不取，因此共有$2^n$中分法。

合并所有有交集的区间后，还剩多少个区间：

很简单，将所有区间排个序（开始时间小的优先，结束时间顺序随意）并遍历。

使用一个变量$lastTo$来记录上一个合并后的区间最右边的元素（初始值为“无穷小”）。

遍历过程中如果当前区间的最左边元素大于$lastTo$，则两个区间无法合并，区间数加一；否则区间数不变。

遍历过程中更新$lastTo$。

sort(ranges.begin(), ranges.end());
int lastTo = -1;
int cnt = 0;  // 合并后的区间数
for (vector<int>& range : ranges) {
    if (range[0] > lastTo) {
        cnt++;
    }
    lastTo = max(lastTo, range[1]);
}

具体实现

按照上述思路，确定好合并后的区间数量后（假设为$cnt$），计算$2^{cnt}\mod 1000000007$即为答案。

我们只需要：

int ans = 1;
for (int i = 0; i < cnt; i++) {
    ans = ans * 2 % mod;
}

但不难发现，其实我们可以直接在$cnt$加一的时候顺便将$ans\times 2$，因此可写为：

sort(ranges.begin(), ranges.end());
int lastTo = -1;
int ans = 1;
for (vector<int>& range : ranges) {
    if (range[0] > lastTo) {
        ans = ans * 2 % MOD;
    }
    lastTo = max(lastTo, range[1]);
}

时空复杂度

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N\log N)$

AC代码

C++

const int MOD = 1e9 + 7;
class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        sort(ranges.begin(), ranges.end());
        int lastTo = -1;
        int ans = 1;
        for (vector<int>& range : ranges) {
            if (range[0] > lastTo) {
                ans = ans * 2 % MOD;
            }
            lastTo = max(lastTo, range[1]);
        }
        return ans;
    }
};

Python

from typing import List


MOD = int(1e9) + 7

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort()
        lastTo = -1
        ans = 1
        for from_, to in ranges:
            if from_ > lastTo:
                ans = ans * 2 % MOD
            lastTo = max(lastTo, to)
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/137074790