Intuition explained with example | Merging intervals | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe question is similar to the merge intervals problem so it would be great if you solv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe question is similar to the [merge intervals](https://leetcode.com/problems/merge-intervals/) problem so it would be great if you solve that one first. \n\nNow, we are given a vector of intervals and the intervals can be overlapping. We need to count the ways in which they can be grouped so that overlapping ranges belong to same group and each range is in only one group at a time. To make the overlapping ranges belong to same group, we can combine the overlapping ranges. \n\nAfter combining overlapping ranges, only the non overlapping ranges would be remaining. Now to count the ways, one range can belong to either group 1 or group 2. To group \'n\' items into 2 groups, there are (2 ^ n) possible ways. So, there are **2^(number of non overlapping ranges)** way of grouping the elements\n\n### Example\n```[1,5], [9,10], [2,3], [6,8]```\n1. Sorting in increasing order of first element:\n```[1,5], [2,3], [6,8], [9,10]```\n2. Combining overlapping ranges: \n```5<2 hence [1,5], [2,3] becomes [1,5].```\n```[1,5], [6,8], [9,10]``` is the final range array\n3. Now, we have non-overlapping invervals which can be grouped in the following ways:\n```\ngroup 1: [1,5], [6,8], [9,10] and group 2 empty\ngroup 1: empty and group 2:[1,5], [6,8], [9,10]\ngroup 1: [1,5], [6,8] and group 2: [9,10]\ngroup 1: [1,5] and group 2: [6,8], [9,10]\ngroup 1: [6,8] and group 2: [1,5], [9,10]\ngroup 1: [9,10] and group 2:[1,5], [6,8]\ngroup 1: [1,5], [9,10] and group 2: [6,8]\ngroup 1: [6,8], [9,10] and group 2: [1,5]\n\n```\n=> count= 2^(number of non overlapping intervals)= 2^3= 8\n\n# Complexity\n- Time complexity: **O(n(logn)**) for sorting, as other time complexities involved are less than or equal to O(n) only\n\n- Space complexity: **O(1)**\n\n# Code\n```\nclass Solution {\npublic:\n\n    int countWays(vector<vector<int>>& ranges) {\n        sort(ranges.begin(),ranges.end()); //sorting so that we can find overlapping intervals\n        vector<int>nonoverlap=ranges[0]; // stores the [start,end] of last non-overlapping interval\n        int k=1,mod = 1e9 + 7; // k counts how many non overlapping intervals we have \n\n        for(int i=1;i<ranges.size();i++){\n            if(ranges[i][0]<=nonoverlap[1]){ // if there\'s overlapping, replace the end value\n                nonoverlap[1]=max(nonoverlap[1],ranges[i][1]);\n            }\n            else {\n                nonoverlap=ranges[i]; // in case of no overlapping with last interval, update the latest interval\n                k++; // increase the count of non overlapping intervals\n            }\n        }\n        int ans=1;\n        while(k--){\n            ans=ans*2%mod; //this can be done in the loop, i\'m doing it outside for better understanding\n        }\n        return ans;\n    }\n};\n```
['C++']