C++ | balanced tree | ordered map | iterator
Complexity

Time complexity: O(logn + k)


Space complexity: O(1);

Code
# Complexity
- Time complexity: O(logn + k)

- Space complexity: O(1);

# Code
```cpp []
class CountIntervals {
public:
    CountIntervals() : counter(0) {
        
    }
    
    void add(int left, int right) {
        auto it = intervals.lower_bound(left);

        if (it != intervals.begin()) {
            if (auto prevIt = std::prev(it); prevIt->second >= left) {
                left = prevIt->first;
                right = std::max(right, prevIt->second);
                counter -= prevIt->second - prevIt->first + 1;
                intervals.erase(prevIt);
            }
        }

        while (it != intervals.end() && right >= it->first) {
            right = std::max(right, it->second);
            counter -= it->second - it->first + 1;
            it = intervals.erase(it);
        }

        intervals[left] = right;
        counter += right - left + 1;
    }
    
    int count() {
        return counter;
    }

private:
    std::map<int, int> intervals;
    int counter;
};

/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals* obj = new CountIntervals();
 * obj->add(left,right);
 * int param_2 = obj->count();
 */
```
['Binary Search Tree', 'Ordered Map', 'Iterator', 'C++']