Merge Intervals + Power in Modulo
QUICK HINTS:\n1. Try thinking after merging the overlapping ranges\n2. Try to think of choices you have\n4. Make sure to take into consideration Modulo\n\nSTEPS
**QUICK HINTS**:\n1. Try thinking after merging the overlapping ranges\n2. Try to think of choices you have\n4. Make sure to take into consideration Modulo\n\n**STEPS:**\n1. We first merge the intervals OR count number of disjoint intervals (say n).\n2. Now for each disjoint interval we have 2 choices (EACH). \n3. Hence, Possible ways = 2^n\n\n\n [**HOW TO MERGE INTERVALS**](https://leetcode.com/problems/merge-intervals/)\n\n**CODE:**\n**Function to calculate power with modulo**\n```\nint power(long long x, int y, int p){\n        int res = 1;\n        x = x % p; \n        if (x == 0) return 0;\n        while (y > 0){\n            if (y & 1)res = (res*x) % p;\n            \n            y = y>>1; // y = y/2\n            x = (x*x) % p;\n        }\n        return res;\n    }\n```\n\n**Function to merge intervals**\n\n```\nvector<vector<int>> merge(vector<vector<int>>& interval) {\n        sort(interval.begin(),interval.end());\n        vector<vector<int>> re;\n        if(interval.size()==0)\n            return re;\n        vector<int> temp=interval[0];\n        \n        for(auto it: interval){\n            if(it[0]<=temp[1]){\n                temp[1]=max(temp[1],it[1]);\n                \n            }\n            else{\n                re.push_back(temp);\n                temp=it;\n            }\n        }\n        re.push_back(temp);\n        return re;\n    }\n```\n\n**Count Ways function**\n\n```\nint countWays(vector<vector<int>>& ranges) {\n        ranges=merge(ranges);\n        int n=ranges.size();\n        return power(2,n,1000000007);\n    }\n```\n
[]