One ordered map 491ms beats 97%
Data Structure\nUse ordered map, also called tree map, to store all the intervals.\nThe map has key=right and value=left. \nUsing right as key is helpful for la
##### Data Structure\nUse ordered map, also called tree map, to store all the intervals.\nThe map has key=right and value=left. \nUsing `right` as key is helpful for later binary search by calling lower_bound()\nAnother int value to store the total count\n\n##### Algorithm\n1. Binary search to find the closest intervals by `left`\n2. Check if the found interval has intersection with new segment `[left, right]`\n3. Cover the new segment by extending the left margin (also increasing the `count` in the mean time)\n4. If there is still some segment not covered, repeat 2~4 for next iteration\n5. After the iteration if there is still some segment not covered, add it into the tree map\n\n##### C++\n```\nclass CountIntervals {\npublic:\n    CountIntervals() {\n\n    }\n\n    void add(int left, int right) {\n        auto it = m.lower_bound(left);\n\n        while (it != m.end() && left <= right) {\n            auto &sl = it->second; // segment left\n            auto &sr = it->first;  // segment right\n\n            if (right < sl) { // no intersection\n                break;\n            }\n\n            // extend left margin to cover the left part of new sement\n            if (left < sl) {\n                cnt += sl - left;\n                sl = left;\n            }\n\n            // move left to the un-covered part for next iteration\n            left = min(sr, right)+1;\n\n            ++it;\n        }\n\n        if (left <= right) {\n            cnt += right-left+1;\n            m[right] = left;\n        }\n    }\n\n    int count() {\n        return cnt;\n    }\n\nprivate:\n    map<int, int> m; // right -> left\n    int cnt = 0;\n};\n```
['Tree', 'C']