What is the core pattern for solving Count Ways to Group Overlapping Ranges?

The core pattern is sorting the ranges and then checking for overlaps, followed by calculating the valid ways to group the ranges based on these overlaps.

How do I count the number of valid groupings?

After sorting and detecting overlaps, you calculate the valid groupings by considering each non-overlapping range as a separate group and counting the possible splits.

What is the time complexity of the optimal solution?

The optimal solution has a time complexity of O(n log n) due to sorting, followed by a linear scan to check overlaps.

Can this problem be solved without sorting the ranges?

Sorting the ranges is essential to efficiently detect overlaps and reduce the complexity of the solution. Without sorting, overlap detection becomes much more difficult and inefficient.

What are the common mistakes when solving Count Ways to Group Overlapping Ranges?

Common mistakes include not sorting the ranges first, failing to properly detect all overlaps, and overcomplicating the counting of valid groupings.

#2580

Medium

auto_awesome数组·排序

LeetCode 题解工作台

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

给你一个二维整数数组 ranges ，其中 ranges[i] = [start i , end i ] 表示 start i 到 end i 之间（包括二者）的所有整数都包含在第 i 个区间中。你需要将 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⁹

lightbulb

解题思路

方法一：排序 + 计数 + 快速幂

我们可以先对区间进行排序，相交的区间进行合并，统计有多少个不相交的区间，记为 $cnt$ 。

每个不相交的区间可以选择放在第一组或第二组，所以方案数为 $2^{cnt}$ 。注意到 $2^{cnt}$ 可能很大，所以需要对 $10^9 + 7$ 取模。这里可以使用快速幂求解。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为区间个数。

我们也可以不使用快速幂，一旦发现有新的不相交的区间，就将方案数乘 $2$ 后对 $10^9 + 7$ 取模。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort()
        cnt, mx = 0, -1
        for start, end in ranges:
            if start > mx:
                cnt += 1
            mx = max(mx, end)
        mod = 10**9 + 7
        return pow(2, cnt, mod)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate use sorting efficiently to simplify the range checking process?
question_mark
Does the candidate recognize the need for efficient overlap detection?
question_mark
Is the candidate able to count valid groupings after determining overlap regions?

warning

常见陷阱

外企场景

error
Failing to sort the ranges before checking overlaps, which leads to inefficient or incorrect results.
error
Not correctly identifying all overlapping ranges, which can result in fewer valid groupings than expected.
error
Overcomplicating the solution with unnecessary computations or missing the core combinatorial counting aspect.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Can the candidate solve the problem with more than two groups of non-overlapping ranges?
arrow_right_alt
What if ranges could be merged into more than one valid group?
arrow_right_alt
How would the approach change if you needed to track the exact groupings rather than just counting them?

help

常见问题

外企场景

继续练习

#2576 求出最多标记下标 #2587 重排数组以得到最大前缀分数 #2589 完成所有任务的最少时间