LeetCode 2580.统计将重叠区间合并成组的方案数：排序（几行代码解决）—

本文主要是介绍LeetCode 2580.统计将重叠区间合并成组的方案数：排序（几行代码解决）——一步步思路描述版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

给你一个二维整数数组 ranges ，其中 ranges[i] = [start_i, end_i] 表示 start_i 到 end_i 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成两个组（可以为空），满足：

每个区间只属于一个组。
两个有交集的区间必须在 同一个 组内。

如果两个区间有至少一个公共整数，那么这两个区间是 有交集 的。

比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。

请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 10⁹ + 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⁵
ranges[i].length == 2
0 <= start_i <= end_i <= 10⁹

方法一：排序

思路

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

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

方法

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

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

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

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

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

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

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

遍历过程中更新 $l a s tT o$ 。

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]);
}

具体实现

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

我们只需要：

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

但不难发现，其实我们可以直接在 $c n t$ 加一的时候顺便将 $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 ListMOD = int(1e9) + 7class Solution:def countWays(self, ranges: List[List[int]]) -> int:ranges.sort()lastTo = -1ans = 1for from_, to in ranges:if from_ > lastTo:ans = ans * 2 % MODlastTo = max(lastTo, to)return ans