C++ Easy BST Recursion
The idea is simple.\nBefore insert new interval, check any previous intervals overlap.\nIf any, remove these intevals and recurse with merged interval.\n\nTime 
The idea is simple.\nBefore insert new interval, check any previous intervals overlap.\nIf any, remove these intevals and recurse with merged interval.\n\n**Time Complexity**\nBest: O(log n) per add call\nWorst: O(n log n) per add call\n* Worst case can be optimized to O(n) with iterative approach: [Merge-intervals](https://leetcode.com/problems/count-integers-in-intervals/discuss/2039706/Merge-Intervals)\n\n```\nclass CountIntervals {\nprivate:\n    int cnt;\n    set<pair<int, int>> pool;\n    \npublic:\n    CountIntervals() {\n        cnt = 0;        \n    }\n    \n    void add(int left, int right) {\n        auto it = pool.lower_bound({left, right});\n        if (it != pool.end()) {\n            auto [qleft, qright] = *it;\n            if (qleft <= right) {\n                cnt -= qright - qleft + 1;\n                pool.erase(it);\n                add(left, max(right, qright));\n                return;\n            }\n        }\n        if (it != pool.begin()) {\n            auto [pleft, pright] = *(--it);\n            if (pright >= left) {\n                cnt -= pright - pleft + 1;\n                pool.erase(it);\n                add(pleft, max(pright, right));\n                return;\n            }\n        }\n        cnt += right - left + 1;\n        pool.insert({left, right});\n    }\n    \n    int count() {\n        return cnt;\n    }\n};\n```\n
['Binary Search Tree', 'Recursion', 'C']