Leetcode-2580-统计将重叠区间合并成组的方案数-c++

题目详见https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/

题目要求将最后的ranges分为两个组。也就是说当你的ranges已经满足题目要求的时候，这两个组怎么分是随意的，这里也就引出了 $2^k$ 的由来，其实就是每组都有2种不同的选择（取，不取）然后取k次。

关键是这里的一个区间合并操作

首先进行Sort之后大致上是这样的

sort(ranges.begin(), ranges.end());

ranges是一个二维向量,每个内层向量表示一个区间,格式是[开始位置,结束位置]。
sort函数对ranges进行排序时,是根据区间的开始位置来排序的:
首先判断两个区间的开始位置,如果开始位置不同,则按开始位置从小到大排序
如果两个区间开始位置相同,则比较结束位置,结束位置较大的放后面
具体排序规则可以这样理解:

若区间A[s1, e1], B[s2, e2]
如果s1 < s2,则A排前面
如果s1 = s2,且e1 < e2,则A排前面

排序完之后的图’大致’是这样的

after_sort

然后执行向右merge操作，结束后大致如下，不同颜色代表不同的range

在这里插入图片描述

注释代码

class Solution {
public:
	// 题目要求：请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。
    static constexpr int mod = 1e9 + 7;
    int countWays(vector<vector<int>>& ranges) {
    	// 这里的sort请看上面的解释
        sort(ranges.begin(), ranges.end());
        int n = ranges.size();
        long long res = 1;
        for (int i = 0; i < n; ) {
            int r = ranges[i][1];	// 右侧端点[1]
            int j = i + 1;	// 下一个range
            // 不断地向右延申直到下一组
            while (j < n && ranges[j][0] <= r) {
                r = max(r, ranges[j][1]);
                j++;
            }
            // 这里其实就是2的k次方
            res = res * 2 % mod;
            i = j;
        }
        return res;
    }
};