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

链接：2580.统计将重叠区间合并成组的方案数
难度：Medium
标签：数组、排序
简介：请你返回将 ranges 划分成两个组的 总方案数 。

题解 1 - python

• 编辑时间：2024-03-27
• 执行用时：120ms
• 内存消耗：45.1MB
• 编程语言：python
• 解法介绍：并查集合并区间。

class UnionFind:
        def __init__(self, n) -> None:
            self.n = n
            self.data = [i for i in range(0, n)]
            self.sizes = [1] * n
            self.cnt = n
        def size(self, v: int) -> int:
            return self.sizes[self.find(v)]
        def find(self, v: int) -> int:
            if self.data[v] != v:
                self.data[v] = self.find(self.data[v])
            return self.data[v]
        def uni(self, v1: int, v2: int):
            p1 = self.find(v1)
            p2 = self.find(v2)
            if p1 != p2:
                self.sizes[p1] += self.sizes[p2]
                self.cnt -= self.sizes[p2]
                self.data[p2] = p1
        def same(self, v1: int, v2: int):
            return self.find(v1) == self.find(v2)
    class Solution:
        def countWays(self, ranges: List[List[int]]) -> int:
            n = len(ranges)
            ranges.sort()
            uf = UnionFind(n)
            idx = 0
            while idx < n:
                start, end = ranges[idx]
                while idx + 1 < n and ranges[idx + 1][0] <= end:
                    end = max(end, ranges[idx + 1][1])
                    uf.uni(idx, idx + 1)
                    idx += 1
                idx += 1
            return (2 ** uf.cnt) % (10 ** 9 + 7)

题解 2 - python

• 编辑时间：2024-03-27
• 执行用时：94ms
• 内存消耗：45.06MB
• 编程语言：python
• 解法介绍：排序后合并区间。

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        n = len(ranges)
        ranges.sort()
        idx = 0
        cnt = 0
        while idx < n:
            start, end = ranges[idx]
            cnt += 1
            while idx + 1 < n and ranges[idx + 1][0] <= end:
                end = max(end, ranges[idx + 1][1])
                idx += 1
            idx += 1
        return pow(2, cnt, 10 ** 9 + 7)