Welcome to Subscribe On Youtube
2580. Count Ways to Group Overlapping Ranges
Description
You are given a 2D integer array ranges where ranges[i] = [starti, endi] denotes that all integers between starti and endi (both inclusive) are contained in the ith range.
You are to split ranges into two (possibly empty) groups such that:
- Each range belongs to exactly one group.
- Any two overlapping ranges must belong to the same group.
Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.
- For example,
[1, 3]and[2, 5]are overlapping because2and3occur in both ranges.
Return the total number of ways to split ranges into two groups. Since the answer may be very large, return it 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.
Constraints:
1 <= ranges.length <= 105ranges[i].length == 20 <= starti <= endi <= 109
Solutions
Solution 1: Sorting + Counting + Fast Power
We can first sort the intervals in the range, merge the overlapping intervals, and count the number of non-overlapping intervals, denoted as $cnt$.
Each non-overlapping interval can be chosen to be put in the first group or the second group, so the number of plans is $2^{cnt}$. Note that $2^{cnt}$ may be very large, so we need to take modulo $10^9 + 7$. Here, we can use fast power to solve this problem.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the number of intervals.
Alternatively, we can also avoid using fast power. Once a new non-overlapping interval is found, we multiply the number of plans by 2 and take modulo $10^9 + 7$.
-
class Solution { public int countWays(int[][] ranges) { Arrays.sort(ranges, (a, b) -> a[0] - b[0]); int cnt = 0, mx = -1; for (int[] e : ranges) { if (e[0] > mx) { ++cnt; } mx = Math.max(mx, e[1]); } return qpow(2, cnt, (int) 1e9 + 7); } private int qpow(long a, int n, int mod) { long ans = 1; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ans = ans * a % mod; } a = a * a % mod; } return (int) ans; } } -
class Solution { public: int countWays(vector<vector<int>>& ranges) { sort(ranges.begin(), ranges.end()); int cnt = 0, mx = -1; for (auto& e : ranges) { cnt += e[0] > mx; mx = max(mx, e[1]); } using ll = long long; auto qpow = [&](ll a, int n, int mod) { ll ans = 1; for (; n; n >>= 1) { if (n & 1) { ans = ans * a % mod; } a = a * a % mod; } return ans; }; return qpow(2, cnt, 1e9 + 7); } }; -
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) -
func countWays(ranges [][]int) int { sort.Slice(ranges, func(i, j int) bool { return ranges[i][0] < ranges[j][0] }) cnt, mx := 0, -1 for _, e := range ranges { if e[0] > mx { cnt++ } if mx < e[1] { mx = e[1] } } qpow := func(a, n, mod int) int { ans := 1 for ; n > 0; n >>= 1 { if n&1 == 1 { ans = ans * a % mod } a = a * a % mod } return ans } return qpow(2, cnt, 1e9+7) } -
function countWays(ranges: number[][]): number { ranges.sort((a, b) => a[0] - b[0]); let mx = -1; let ans = 1; const mod = 10 ** 9 + 7; for (const [start, end] of ranges) { if (start > mx) { ans = (ans * 2) % mod; } mx = Math.max(mx, end); } return ans; }