2024.3.27力扣每日一题——统计将重叠区间合并成组的方案数

本文主要是介绍2024.3.27力扣每日一题——统计将重叠区间合并成组的方案数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.3.27

- - 题目来源
  - 我的题解
  - - 方法一排序+合并区间+快速幂
    - 方法二官方区间合并

题目来源

力扣每日一题；题序：2580

我的题解

方法一排序+合并区间+快速幂

先将ranges按第一个元素升序，再按第二个元素升序。然后采用合并区间的方式进行区间合并，每次有区间合并n都减1，最后计算 $2^n$ %1000000007就可以得到最终的答案。但是由于n可能很大，所以直接计算 $2^n$ 会出现long类型溢出，所以需要再计算过程中一直mod，即如fastPow函数。

时间复杂度：O(nlogn)。主要是排序消耗的时间
空间复杂度：O(logn)。排序所用的栈空间为 O(log⁡n)。

public  int countWays(int[][] ranges) {Arrays.sort(ranges,(a,b)->{if(a[0]==b[0])return a[1]-b[1];elsereturn a[0]-b[0];});int n=ranges.length;int mod=1000000007;int sz=n;int min=ranges[0][0];int max=ranges[0][1];for(int i=1;i<sz;i++){int[] t=ranges[i];if((t[0]>=min&&t[0]<=max)||(t[1]>=min&&t[1]<=max)){n--;min=Math.min(min,t[0]);max= Math.max(max,t[1]);}else{min=t[0];max=t[1];}}long res=fastPow(2,n,mod);return (int)(res%mod);}public   long fastPow(int x,int n,int mod){long res = 1;while(n>0){if((n&1)==1){res=(res*x)%mod;}x=(int)((long)x*x%mod);n>>=1;}return res;}

方法二官方区间合并

参考官方题解

时间复杂度：O(nlogn)
空间复杂度：O(logn)

static final int MOD = 1000000007;public int countWays(int[][] ranges) {Arrays.sort(ranges, (a, b) -> a[0] - b[0]);int n = ranges.length;int res = 1;for (int i = 0; i < n; ) {int r = ranges[i][1];int j = i + 1;while (j < n && ranges[j][0] <= r) {r = Math.max(r, ranges[j][1]);j++;}res = res * 2 % MOD;i = j;}return res;
}