We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Ways to Group Overlapping Ranges

Number: 2651

Difficulty: Medium

Paid? No

Companies: IBM, Oracle

Problem Description

Given an array of ranges, where each range is represented by an inclusive pair [start, end], split the ranges into two (possibly empty) groups such that each range is assigned to exactly one group and any two overlapping ranges are placed in the same group. Two ranges are considered overlapping if they share at least one integer. Return the total number of ways to split the ranges into two groups mod 10^9 + 7.

Key Insights

  • Overlapping ranges create dependencies and must reside in the same group.
  • The ranges can be seen as forming connected components where each component represents a set of ranges that are connected through overlaps.
  • Each connected component can be assigned independently to either group, giving 2 choices per component.
  • The final answer is 2^K where K is the number of connected components.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the ranges.
Space Complexity: O(n) for storing sorted ranges and performing the merge operation.

Solution

The solution involves first sorting the ranges based on the start value. Then, we merge overlapping intervals to identify different connected components. When iterating through the sorted list, if the current range overlaps with the previous merged range (i.e. its start is less than or equal to the current component's end), we merge it by updating the end of the component. Otherwise, we have identified a new component. Once the number of components is determined, the answer is computed as 2 raised to the power of the number of components, modulo 10^9 + 7.

The data structures used include:

  • A list (or array) for storing and sorting the ranges.
  • Variables to maintain the current component's boundaries and count of components.

Algorithmic steps:

  1. Sort ranges by their starting point.
  2. Initialize a counter for connected components.
  3. Iterate through the sorted ranges, merging overlapping intervals.
  4. Each time a non-overlapping range is encountered, increase the component count.
  5. Return the result as 2^components mod 10^9 + 7.

Code Solutions

# Define a constant for modulo operation
MOD = 10**9 + 7

def countWays(ranges):
    # Sort the list of ranges by their starting point
    ranges.sort(key=lambda interval: interval[0])
    
    # Initialize the count of connected components
    components = 0
    # current_end will track the end of the current connected component
    current_end = -1
    
    # Iterate over the sorted ranges
    for start, end in ranges:
        # If the current component is empty or the current range does not overlap
        if start > current_end:
            components += 1  # Increase the component count
            current_end = end  # Start a new component with current range
        else:
            # Merge the overlapping interval by updating the current_end
            current_end = max(current_end, end)
    
    # Calculate 2^components mod MOD
    return pow(2, components, MOD)

# Example usage:
print(countWays([[6,10],[5,15]]))  # Expected Output: 2
print(countWays([[1,3],[10,20],[2,5],[4,8]]))  # Expected Output: 4
← Back to All Questions