Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2580.html

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 because 2 and 3 occur 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 <= 105
  • ranges[i].length == 2
  • 0 <= 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 qmi(2, cnt, (int) 1e9 + 7);
        }
    
        int qmi(long a, long k, int p) {
            long res = 1;
            while (k != 0) {
                if ((k & 1) == 1) {
                    res = res * a % p;
                }
                k >>= 1;
                a = a * a % p;
            }
            return (int) res;
        }
    }
    
  • 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]);
            }
            return qmi(2, cnt, 1e9 + 7);
        }
    
        int qmi(long a, long k, int p) {
            long res = 1;
            while (k != 0) {
                if ((k & 1) == 1) {
                    res = res * a % p;
                }
                k >>= 1;
                a = a * a % p;
            }
            return res;
        }
    };
    
  • 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]
    		}
    	}
    	return qmi(2, cnt, 1e9+7)
    }
    
    func qmi(a, k, p int) int {
    	res := 1
    	for k != 0 {
    		if k&1 == 1 {
    			res = res * a % p
    		}
    		k >>= 1
    		a = a * a % p
    	}
    	return res
    }
    
  • 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;
    }
    
    

All Problems

All Solutions