Count Ways to Group Overlapping Ranges

medium array sorting intervals

Problem

You are given a list of ranges where ranges[i] = [starti, endi] is inclusive. Two ranges are considered connected if they overlap (share at least one point). Connectivity is transitive: ranges that are chained together by overlaps all belong to one group. Split every range into one of two sets so that any two ranges that overlap end up in the same set. Return the number of valid ways to do this, modulo 10^9 + 7.

Inputranges = [[1,2],[2,3],[4,5]]

Output4

[1,2] and [2,3] overlap, so they form one group; [4,5] is alone. With 2 independent groups and 2 choices each, there are 2² = 4 ways.

ranges (semicolon-separated, "a,b")

def count_ways(ranges):
    MOD = 1_000_000_007
    ranges.sort(key=lambda x: x[0])
    groups = 0
    cur_end = -1
    for s, e in ranges:
        if s > cur_end:
            groups += 1
        cur_end = max(cur_end, e)
    return pow(2, groups, MOD)

function countWays(ranges) {
  const MOD = 1000000007n;
  ranges.sort((a, b) => a[0] - b[0]);
  let groups = 0, curEnd = -1;
  for (const [s, e] of ranges) {
    if (s > curEnd) groups++;
    curEnd = Math.max(curEnd, e);
  }
  let ans = 1n;
  for (let i = 0; i < groups; i++) ans = (ans * 2n) % MOD;
  return Number(ans);
}

class Solution {
    public int countWays(int[][] ranges) {
        long MOD = 1000000007L;
        Arrays.sort(ranges, (a, b) -> Integer.compare(a[0], b[0]));
        int groups = 0, curEnd = -1;
        for (int[] r : ranges) {
            if (r[0] > curEnd) groups++;
            curEnd = Math.max(curEnd, r[1]);
        }
        long ans = 1;
        for (int i = 0; i < groups; i++) ans = (ans * 2) % MOD;
        return (int) ans;
    }
}

int countWays(vector<vector<int>>& ranges) {
    long MOD = 1000000007L;
    sort(ranges.begin(), ranges.end(), [](auto& a, auto& b){ return a[0] < b[0]; });
    int groups = 0, curEnd = -1;
    for (auto& r : ranges) {
        if (r[0] > curEnd) groups++;
        curEnd = max(curEnd, r[1]);
    }
    long ans = 1;
    for (int i = 0; i < groups; i++) ans = (ans * 2) % MOD;
    return (int) ans;
}

Explanation

The rule "overlapping ranges must land in the same set" means each connected group of ranges moves as a single block. Inside a group there is no freedom — every range follows the rest. Between groups there is full freedom: each group can go into set 1 or set 2 independently.

So if there are g independent groups, every group has 2 choices, giving 2 × 2 × … = 2^g total ways. All we really need is the count of groups, taken modulo 10^9 + 7.

To count groups we reuse the classic interval-merge sweep. Sort by start, then walk left to right tracking cur_end, the farthest end reached by the current group. When a new range starts after cur_end (s > cur_end), it cannot touch anything before it, so it begins a fresh group and we bump the counter. Either way we extend cur_end with max(cur_end, e) so a long range keeps later overlaps in the same group.

Example: [[1,2],[2,3],[4,5]]. [1,2] opens group 1 (cur_end = 2). [2,3] starts at 2, not greater than cur_end, so it joins group 1 (cur_end = 3). [4,5] starts at 4 > 3, so it opens group 2. Two groups → 2^2 = 4.

The power is computed with fast modular exponentiation (or a simple doubling loop) to stay within the modulus, which keeps everything fast even for large inputs.

Time: O(n log n) Space: O(1)