LeetCode in Kotlin

2580. Count Ways to Group Overlapping Ranges

Medium

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:

Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.

Return the total number of ways to split ranges into two groups. Since the answer may be very large, return it modulo 109 + 7.

Example 1:

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

Output: 2

Explanation:

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

Thus, there are two possible ways:

Example 2:

Input: ranges = [[1,3],[10,20],[2,5],[4,8]]

Output: 4

Explanation:

Ranges [1,3], and [2,5] are overlapping. So, they must be in the same group.

Again, ranges [2,5] and [4,8] are also overlapping. So, they must also be in the same group.

Thus, there are four possible ways to group them:

Constraints:

Solution

@Suppress("NAME_SHADOWING")
class Solution {
    fun countWays(ranges: Array<IntArray>): Int {
        var cnt = 1
        ranges.sortWith { a, b -> if (a[0] != b[0]) a[0] - b[0] else a[1] - b[1] }
        var curr = ranges[0]
        for (i in 1 until ranges.size) {
            if (ranges[i][1] < curr[0] || ranges[i][0] > curr[1]) {
                ++cnt
                curr = ranges[i]
            } else {
                curr[1] = Math.max(curr[1], ranges[i][1])
            }
        }
        return powMod(2, cnt.toLong()).toInt()
    }

    private fun powMod(b: Long, e: Long): Long {
        var b = b
        var e = e
        var ans: Long = 1
        while (e != 0L) {
            if (e and 1L == 1L) {
                ans *= b
                ans %= MOD.toLong()
            }
            b *= b
            b %= MOD.toLong()
            e = e shr 1
        }
        return ans
    }

    companion object {
        var MOD = 1e9.toInt() + 7
    }
}