统计将重叠区间合并成组的方案数

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

/*
 * Problem: Given a 2D integer array 'ranges' where ranges[i] = [start_i, end_i] 
 * indicates that all integers from start_i to end_i (inclusive) are covered 
 * by the i-th interval.
 * We need to split 'ranges' into two groups such that:
 * 1. Each interval belongs to exactly one group.
 * 2. Intervals with intersection must be in the same group.
 * The task is to return the number of ways to split 'ranges' into two groups,
 * with the result modulo 10^9 + 7.
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    private static final int MOD = 1_000_000_007;

    public int countWays(int[][] ranges) {
        // Sort intervals based on their start times
        Arrays.sort(ranges, Comparator.comparingInt(a -> a[0]));

        int totalGroups = (int) IntStream.range(0, ranges.length - 1)
                .filter(i -> ranges[i + 1][0] > ranges[i][1])
                .count() + 1;

        // There are 2^totalGroups ways to assign groups
        long result = IntStream.range(0, totalGroups)
                .mapToLong(i -> 2)
                .reduce(1, (a, b) -> (a * b) % MOD);

        return (int) result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] ranges1 = {{6, 10}, {5, 15}};
        int[][] ranges2 = {{1, 3}, {10, 20}, {2, 5}, {4, 8}};
        System.out.println(sol.countWays(ranges1)); // Output: 2
        System.out.println(sol.countWays(ranges2)); // Output: 4
    }
}

题解中采用了图的连通分量的思想。首先，通过对区间按照起始点进行排序，确保处理顺序的逻辑性。在遍历排序后的区间时，用一个变量bound来维持当前已遍历区间的最大结束点。如果当前区间的起始点大于bound，说明此区间与之前的区间不连续，即形成了一个新的连通分量。变量n记录这样的连通分量的数量。每一个连通分量都可以独立选择放在两个不同的组中，因此最终的方案数是2的n次幂，使用pow函数可以高效地计算模1_000_000_007下的结果。

O(n log n)

O(1)