C++ - Math Combinatorics
Intuition\n1. we need to merge overlapping ranges and find total number of non-overlapping ranges. \n2. If there are total 4 non overlapping than you can devide
# Intuition\n1. we need to merge overlapping ranges and find total number of non-overlapping ranges. \n2. If there are total 4 non overlapping than you can devide them into 2^4 way into two groups. \nEmpty first group and 4 elements into second group: \n    Total number of ways:1\n1 element in first group and 3 elements into second group : \n    Total number of ways: Select 1 element from 4 (1C4)=4\n2 element in first group and 2 elements into second group : \n    Total number of ways: Select 2 element from 4 (2C4)=6\n3 element in first group and 1 elements into second group : \n    Total number of ways: Select 1 element from 4 (3C4)=4\n4 element in first group and 0 elements into second group : \n    Total number of ways: Select 4 element from 4 (4C4)=1\n\nTotal: 1+4+6+4+1 = 16 (2^4(number of elements))\n\nMore info about picking r elements from n: https://www.calculatorsoup.com/calculators/discretemathematics/combinations.php\n\n# Code\n```\nclass Solution {\npublic:\n    int countWays(vector<vector<int>>& ranges) {\n        sort(ranges.begin(),ranges.end());\n        vector<vector<int>> ans;\n        int ret=1;\n        for (auto& r: ranges){\n            if (ans.empty() || ans.back()[1]<r[0]) ans.push_back(r),ret = (ret*2)%1000000007;\n            else ans.back()[1] = max(ans.back()[1],r[1]);\n        }\n        //for (auto r: ans) cout << r[0] << "-" << r[1] << endl;\n        return ret;\n    }\n};\n```
['C++']