[C++] 2^(merged intervals) O(n log n)
Intuition: Merging According to the problem statement, all overlapping intervals must be in the same partition. Therefore, we can consider the merged interval o
**Intuition: Merging** According to the problem statement, all overlapping intervals must be in the same partition. Therefore, we can consider the merged interval of all overlapping intervals as a single interval.\n**Intuition: 2^N** For each merged interval now, we can make a choice: put it in group 1 or group 2. Thus, we will have 2 choices for each interval. As we continue to make choices, we will have had 2 * 2 * 2 * 2... choices.\nWe will merge all intervals then compute 2^n modulo 1e9+7 to return the final answer. Merging intervals is a classic problem, so you can use a snippet from [here](https://leetcode.com/problems/merge-intervals/discuss/?currentPage=1&orderBy=most_votes&query=) to save time.\n```\nclass Solution {\npublic:\n    vector<vector<int>> merge(vector<vector<int>>& intervals) {\n        sort(intervals.begin(), intervals.end());\n        vector<vector<int>> ans;\n        for(int i = 0; i < intervals.size(); i++){\n            vector<int> current = intervals[i];\n            while(i+1 < intervals.size() && (intervals[i+1][0] <= current[1])){\n                current = {min(current[0], intervals[i+1][0]), max(current[1], intervals[i+1][1])};\n                i++;\n            }\n            ans.push_back(current);\n        }        \n        return ans;\n    }\n    const int MOD = 1e9+7;\n    int countWays(vector<vector<int>>& ranges) {\n        auto v = merge(ranges);\n        long long ans = 1;\n        for(int i = 0; i < v.size(); i++){\n            ans*=2;\n            ans %= MOD;\n        }\n        return ans;\n    }\n\t};
[]