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:
Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.
[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 <= 105ranges[i].length == 20 <= starti <= endi <= 109This approach involves sorting the ranges based on their starting points. After sorting, we iterate through the sorted list, merging overlapping ranges. We count the number of disjoint groups of ranges – every such group is independent and can be assigned to two different groups.
In the code, ranges are sorted based on the start value. As we iterate through the ranges, each time we encounter a start value greater than the current end value, we know a new independent group of ranges has started. The number of such groups is counted and the result is computed as 2 raised to the power of the group count, modulo 10^9 + 7.
Java
Time Complexity: O(n log n) due to sorting, where n is the number of intervals.
Space Complexity: O(1), aside from input storage.
This approach uses the Union-Find data structure to manage groups of overlapping intervals. We treat each range's start and end as part of a graph, unioning connected nodes. The number of separate union sets tells us how many independent range groups we have.
The union-find structure helps classify overlapping ranges efficiently by treating them as connected components. Each unique component is a set of interconnected nodes representing overlapping intervals. By counting different root nodes, we determine the number of independent range groups.
Time Complexity: O(n log n) for sorting, O(n^2) in the worst case for potential full connections.
Space Complexity: O(n) for parent array.
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Merge Overlapping Intervals | Time Complexity: O(n log n) due to sorting, where n is the number of intervals. |
| Approach 2: Disjoint Set Union (Union-Find) Algorithm | Time Complexity: O(n log n) for sorting, O(n^2) in the worst case for potential full connections. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,679 views views
Watch 9 more video solutions →Practice Count Ways to Group Overlapping Ranges with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor