Merge Intervals
We use a map to add new intervals in O(log n). As we add an interval, we need to merge it with the existing ones, and update the counter. That way, the count fu
We use a map to add new intervals in O(log n). As we add an interval, we need to merge it with the existing ones, and update the counter. That way, the `count` function is O(1).\n\nMerging intervals is always tricky. The best is to use pen and paper to go through various scenarios.\n\nWhen we add an interval, we check for overlapping intervals before and after. We extend `left` and `right` accordingly, remove all overlapping intervals, and add the new interval `[left, right]` in the end. This is an example how we merge `[4, 14]` interval with the existing ones:\n- Note that all existing overlapping intervals are removed, and their integers substracted from `cnt`.\n\t- We remove 3 intervals, and subtract `12`  from `cnt`.\n- We extend the new interval to `[2, 15]`.\n- We add the new interval `[2, 15]` and add `14` to the count .\n\t- The new interval resulted in adding `14 - 12 == 2` new integers.  \n\n![image](https://assets.leetcode.com/users/images/b0298dab-b861-4dd9-9904-90cd37e93fca_1652647113.0372255.png)\n\n**C++**\n```cpp\nclass CountIntervals {\npublic:\n    map<int, int> m;\n    int cnt = 0;\n    void add(int left, int right) {\n        auto it = m.upper_bound(left);\n        if (it != begin(m) && prev(it)->second >= left)\n            it = prev(it);\n        for (; it != end(m) && it->first <= right; m.erase(it++)) {\n            left = min(left, it->first);\n            right = max(right, it->second);\n            cnt -= it->second - it->first + 1;\n        }\n        cnt += right - left + 1;\n        m[left] = right;\n    }\n    int count() { return cnt; }\n};\n```\n\n**Java**\n```java\nclass CountIntervals {\n    TreeMap<Integer, Integer> m = new TreeMap<>();\n    int cnt = 0;\n    public void add(int left, int right) {\n        var it = m.floorEntry(left);\n        if (it == null || it.getValue() < left)\n            it = m.higherEntry(left);\n        for (; it != null && it.getKey() <= right; it = m.higherEntry(left)) {\n            left = Math.min(left, it.getKey());\n            right = Math.max(right, it.getValue());\n            cnt -= it.getValue() - it.getKey() + 1;\n            m.remove(it.getKey());\n        }\n        m.put(left, right);\n        cnt += right - left + 1;        \n    }\n    public int count() { return cnt; }\n}\n```
['C', 'Java']