2580. Count Ways to Group Overlapping Ranges Medium

1/**
2 * [2580] Count Ways to Group Overlapping Ranges
3 *
4 * 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 i^th range.
5 * You are to split ranges into two (possibly empty) groups such that:
6 * 
7 * 	Each range belongs to exactly one group.
8 * 	Any two overlapping ranges must belong to the same group.
9 * 
10 * Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.
11 * 
12 * 	For example, [1, 3] and [2, 5] are overlapping because 2 and 3 occur in both ranges.
13 * 
14 * Return the total number of ways to split ranges into two groups. Since the answer may be very large, return it modulo 10^9 + 7.
15 *  
16 * <strong class="example">Example 1:
17 * 
18 * Input: ranges = [[6,10],[5,15]]
19 * Output: 2
20 * Explanation: 
21 * The two ranges are overlapping, so they must be in the same group.
22 * Thus, there are two possible ways:
23 * - Put both the ranges together in group 1.
24 * - Put both the ranges together in group 2.
25 * 
26 * <strong class="example">Example 2:
27 * 
28 * Input: ranges = [[1,3],[10,20],[2,5],[4,8]]
29 * Output: 4
30 * Explanation: 
31 * Ranges [1,3], and [2,5] are overlapping. So, they must be in the same group.
32 * Again, ranges [2,5] and [4,8] are also overlapping. So, they must also be in the same group. 
33 * Thus, there are four possible ways to group them:
34 * - All the ranges in group 1.
35 * - All the ranges in group 2.
36 * - Ranges [1,3], [2,5], and [4,8] in group 1 and [10,20] in group 2.
37 * - Ranges [1,3], [2,5], and [4,8] in group 2 and [10,20] in group 1.
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	1 <= ranges.length <= 10^5
43 * 	ranges[i].length == 2
44 * 	0 <= starti <= endi <= 10^9
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/count-ways-to-group-overlapping-ranges/
50// discuss: https://leetcode.com/problems/count-ways-to-group-overlapping-ranges/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn count_ways(ranges: Vec<Vec<i32>>) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2580() {
68    }
69}
70