#2580
Count Ways to Group Overlapping Ranges
expert · 1025 · lc medium +32 · verified · 39% accepted · 339 likes · top 18%
Description
Given a 2D integer array ranges where each entry [starti, endi] describes a closed interval, partition all ranges into two groups (possibly empty) so that overlapping ranges always belong to the same group. Two ranges overlap if they share at least one integer. Return the number of valid partitions modulo 109 + 7.
Example 1:
Input: ranges = [[6,10],[5,15]]
Output: 2
Explanation:
The two ranges are overlapping, so they must be in the same group.
Thus, there are two possible ways:
- Put both the ranges together in group 1.
- Put both the ranges together in group 2.
Example 2:
Input: ranges = [[1,3],[10,20],[2,5],[4,8]]
Output: 4
Explanation:
Ranges [1,3], and [2,5] are overlapping. So, they must be in the same group.
Again, ranges [2,5] and [4,8] are also overlapping. So, they must also be in the same group.
Thus, there are four possible ways to group them:
- All the ranges in group 1.
- All the ranges in group 2.
- Ranges [1,3], [2,5], and [4,8] in group 1 and [10,20] in group 2.
- Ranges [1,3], [2,5], and [4,8] in group 2 and [10,20] in group 1.
Code
1
2
3