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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges
• 标签: 排序, 快速幂

解法一: 排序, 快速幂

go

const MOD = 1_000_000_007

func countWays(ranges [][]int) int {
  sort.Slice(ranges, func(i, j int) bool {
    return ranges[i][0] <= ranges[j][0]
  })
  count := 0
  pre := -1
  for _, r := range ranges {
    if pre < r[0] {
      count++
    }
    pre = max(pre, r[1])
  }
  return quickSort(2%MOD, count, MOD)
}

func quickSort(num, x, mod int) int {
  if x == 0 {
    return 1
  } else if x == 1 {
    return num % mod
  }
  half := x >> 1
  halfAns := quickSort(num, half, mod)
  ans := halfAns * halfAns % mod
  if (x & 1) == 1 {
    ans = ans * num % mod
  }
  return ans
}