C++ | Set + Binary Search Solution
Task: Implement a data structure which allows you to merge intervals, and gives the count of the number of integers that belong atleast to a single range.\n\nAp
**Task: Implement a data structure which allows you to merge intervals, and gives the count of the number of integers that belong atleast to a single range.**\n\n**Approach:**\nSo, notice that these type of problems involve merging segments/ranges.\nWe begin by taking a set of pairs which would hold the "disjoint" segments inside of it. Notice that we would always be having disjoint segments in our set, so:\nr1 < l2, r2 < l3 .. and so on.\n\nNow, whenever we get a new segment that has to be added to our data structure, we firstly check whether it is overlapping with any of our existing segments, and try to merge this new segment with the existing segments.\n\nHow do you check which existing segments overlap with our current segment?\nWe use binary search to find out the first segment in the set which might be overlapping with the new segment.\nWe just take the lower bound of "left" on the set, and decrease the iterator (think why we\'re decreasing the iterator here).\nThen, we keep iterating until we find a non-overlapping segment.\nWe then erase the existing segments that overlap with the new segment, and add the newly updated segment into the set. \n\nCode: \n```\nclass CountIntervals {\npublic:\n    CountIntervals() {\n        \n    }\n    \n    set<pair<int,int>> s;\n    int cnt = 0;\n    \n    void add(int left, int right) {\n        auto it = s.lower_bound({left, 0});\n        if(it != s.begin()) it--;\n        vector<pair<int,int>> to_erase;\n        int newl = left, newr = right;\n        while(it != s.end()){\n            //check whether *it overlaps with our new seg or not\n            pair<int,int> p = *it;\n            if(p.first > right) break;\n            if(!(right < p.first || p.second < left)){\n                to_erase.push_back(p);\n                newl = min(p.first, newl), newr = max(p.second, newr);\n            }\n            it++;\n        }\n        for(auto p : to_erase){\n            cnt -= (p.second - p.first + 1);\n            s.erase(p);\n        }\n        cnt += (newr - newl + 1);\n        s.insert({newl, newr});\n        \n        // Debugging\n        // for(auto p : s){\n        //     cout << p.first << " " << p.second << endl;\n        // }\n        // cout << cnt << endl;\n        // cout << endl;\n    }\n    \n    int count() {\n        return cnt;\n    }\n};\n\n/**\n * Your CountIntervals object will be instantiated and called as such:\n * CountIntervals* obj = new CountIntervals();\n * obj->add(left,right);\n * int param_2 = obj->count();\n */\n```\n\n**Takeaways**: \nHow do you check whether two segments (l1, r1) and (l2, r2) are overlapping or not?\nIf: r1 < l1 (or) r2 < l2, then the two segments are non-overlapping\nelse: overlapping
['Binary Tree', 'Ordered Set']