[C++] [O(N*log(N))] Simple merge intervals with multimap
This problem can be solved by maintaining non-intersected intervals and counting all covered integers when a new interval is added. When it is added:\n1. Just a
This problem can be solved by maintaining non-intersected intervals and counting all covered integers when a new interval is added. When it is added:\n1. Just add the new interval, and increase `cnt` by the new interval size.\n2. Handle all introduced intersections:\n\t2.1 start with `previous` interval - it is the first which can be affected\n\t2.2 while current interval start is <= `right` - check it, and if it is intersected with the next interval - fix this, maintain `cnt` at the same time.\n\n`multimap<int, int>` is handy here.\n\n```cpp\nclass CountIntervals {\n    multimap<int, int> mm;\n    int cnt = 0;\npublic:\n    void add(int left, int right) {\n        cnt += right - left + 1;\n        mm.insert({left, right + 1});\n        \n        auto it = mm.lower_bound(left);\n        if (it != mm.begin()) {\n            it = prev(it);\n        }\n        while (it != mm.end() && it->first <= right) {\n            auto nextIt = next(it);\n            if (nextIt == mm.end()) break;\n            \n            if (it->second >= nextIt->first) {\n                if (it->second >= nextIt->second) {\n                    cnt -= (nextIt->second - nextIt->first);\n                } else {\n                    cnt -= (it->second - nextIt->first);\n                    it->second = nextIt->second;\n                }\n                mm.erase(nextIt);\n            } else {\n                it = next(it);\n            }\n        }\n    }\n    \n    int count() {\n        return cnt;\n    }\n};\n```
['C']