Counting Connected Components (Beats 100%)
Intuition\nWe can think of the set of ranges as vertices in a graph, with edges between vertices for overlapping ranges. Since every pair of overlapping ranges 
# Intuition\nWe can think of the set of ranges as vertices in a graph, with edges between vertices for overlapping ranges. Since every pair of overlapping ranges must always be in the same set, all ranges in the same connected component of the graph must be in the same group.\n\nEach connected component is in one subset or the other, so given $$k$$ connected components there are $$2^k$$ ways to group the ranges.\n\n# Approach\nWe first sort the ranges by start point. This groups together all connected components. We can then scan forward, keeping track of the greatest end-point we have seen so far. If the start-point of a range is greater than that, then it is the first of a new connected component.\n\nI could optimise the loop that computes $$2^k mod (10^9 + 7)$$, but the performance is dominated by sorting so it doesn\'t matter.\n\n# Complexity\n- Time complexity: $$O(n \\log n)$$, dominated by sorting.\n\n- Space complexity: $$O(n)$$.\n\n# Code\n```cpp []\n#include <numeric>\n#include <algorithm>\n#include <execution>\n#include <utility>\nclass Solution {\npublic:\n    int countWays(vector<vector<int>>& ranges) {\n        // iterate forward and repeatedly partition to count connected components\n        const long mod_base = 1000000007; // 10^9 + 7\n        sort(execution::par_unseq, ranges.begin(), ranges.end(),\n            [](auto &a, auto &b) { return a[0] < b[0]; });\n\n        long long connected_components = 1;\n        int component_end = ranges[0][1];\n        for (size_t i = 1; i < ranges.size(); i++) {\n            if (ranges[i][0] > component_end) {\n                connected_components += 1;\n                component_end = ranges[i][1];\n            } else {\n                component_end = max(component_end, ranges[i][1]);\n            }\n        }\n\n        // return (1 << connected_components) % mod_base;\n        int ways = 1;\n        for (long i = 0; i < connected_components; i++) {\n            ways = (ways << 1) % mod_base;\n        }\n        return ways;\n    }\n};\n```
['Graph', 'C++']