Count Ways to Group Overlapping Ranges — LeetCode 2580 Python Solution

The problem

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.

Example

Input

ranges = [[6,10],[5,15]]

Output

2

Explanation

The two ranges are overlapping, so they must be in the same group.

Python solution

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort()
        cnt, mx = 0, -1
        for start, end in ranges:
            if start > mx:
                cnt += 1
            mx = max(mx, end)
        mod = 10**9 + 7
        return pow(2, cnt, mod)

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2580. Count Ways to Group Overlapping Ranges is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems