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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Ways to Group Overlapping Ranges

Difficulty: Medium

Problem Description

You are given a 2D integer array ranges where ranges[i] = [start_i, end_i] denotes that all integers between start_i and end_i (both inclusive) are contained in the i-th 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. 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.

Key Insights

  • Overlapping ranges must be grouped together.
  • Non-overlapping ranges can be assigned independently to either group.
  • The problem can be represented as a graph where ranges are nodes and edges connect overlapping ranges.
  • The number of connected components in this graph determines the number of ways to split the groups.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the ranges. Space Complexity: O(n) - for storing the adjacency list of the graph.

Solution

To solve the problem, we can follow these steps:

  1. Sort the ranges based on their starting values. If two ranges start at the same point, sort based on their ending value.
  2. Build a graph where each range is a node, and edges represent overlapping ranges.
  3. Use DFS/BFS to find connected components in the graph. Each connected component can be grouped in two ways (either in group 1 or group 2).
  4. The total number of ways to split the ranges is 2 raised to the power of the number of connected components, modulo 10^9 + 7.

Code Solutions

def countWays(ranges):
    MOD = 10**9 + 7
    # Step 1: Sort ranges by starting and then ending values
    ranges.sort()
    
    components = 0
    n = len(ranges)
    visited = [False] * n
    
    # Step 2: Define a DFS function to mark all connected ranges
    def dfs(i):
        stack = [i]
        while stack:
            node = stack.pop()
            for j in range(n):
                if not visited[j] and ranges[node][1] >= ranges[j][0]:  # Check for overlap
                    visited[j] = True
                    stack.append(j)

    # Step 3: Count connected components
    for i in range(n):
        if not visited[i]:
            components += 1
            visited[i] = True
            dfs(i)
    
    # Step 4: Calculate the number of ways
    return pow(2, components, MOD)
← Back to All Questions