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

题目描述：

给你一个二维整数数组 ranges ，其中 ranges[i] = [start_i, end_i] 表示 start_i 到 end_i 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组（可以为空），满足：

• 每个区间只属于一个组。
• 两个有 交集 的区间必须在 同一个 组内。
• 如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。

比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。 请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 10⁹ + 7 取余 后返回。

示例 1：

输入：ranges = [[6,10],[5,15]]
输出：2
解释：
两个区间有交集，所以它们必须在同一个组内。
所以有两种方案：
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。

示例 2：

输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
输出：4
解释：
区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
所以总共有 4 种分组方案：
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。

提示：

• 1 <= ranges.length <= 10⁵
• ranges[i].length == 2
• 0 <= start_i <= end_i <= 10⁹

---

解题分析及思路：

方法：排序 + 快速幂

思路：

首先，按照 56. 合并区间 的思路，对给定的区间数组ranges进行拆分，将其拆分为互不重叠的区间。在拆分过程中，我们确保每个新区间的右端点更新为前一个区间的右端点，以确保新的区间能够正确覆盖已经出现过的区间，从而保证后续的区间判断能够正常进行。

针对每个不重叠的区间，我们有两种选择：将其放入第一组或第二组。由于共有count个不重叠的区间，因此有2^count种可能。 那么可以使用 50. Pow(x, n) 的思想，通过对每个区间的两种选择进行组合，计算出最终结果。

import (
	"sort"
)

const mod = 1e9 + 7

func countWays(ranges [][]int) int {
	sort.Slice(ranges, func(i, j int) bool {
		if ranges[i][0] == ranges[j][0] {
			return ranges[i][1] < ranges[j][1]
		}
		return ranges[i][0] < ranges[j][0]
	})
	var count = 1
	for i := 1; i < len(ranges); i++ {
		if ranges[i][0] > ranges[i-1][1] {
			count++
		} else if ranges[i][1] < ranges[i-1][1] {
			ranges[i][1] = ranges[i-1][1]
		}
	}
	return pow(2, count)
}

func pow(x, num int) int {
	var result = 1
	for num > 0 {
		if num%2 == 1 {
			result *= x
			result %= mod
		}
		x *= x
		x %= mod
		num = num >> 1
	}
	return result
}

复杂度：

• 时间复杂度：O(N * logN)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:127 ms,击败了75.00% 的Go用户
• 内存消耗:15.9 MB,击败了91.67% 的Go用户