2276. Count Integers in Intervals

Given an empty set of intervals, implement a data structure that can:

• Add an interval to the set of intervals.
• Count the number of integers that are present in at least one interval.

Implement the CountIntervals class:

• CountIntervals() Initializes the object with an empty set of intervals.
• void add(int left, int right) Adds the interval [left, right] to the set of intervals.
• int count() Returns the number of integers that are present in at least one interval.

Note that an interval [left, right] denotes all the integers x where left <= x <= right.

c++

class CountIntervals {
    int c = 0;
    map<int, int> intervals;
    map<int, int>::iterator start(int l) {
        auto it = intervals.upper_bound(l);
        if(it == begin(intervals)) {
            return intervals.insert({l,l-1}).first;
        }
        --it;
        if(it->second + 1 >= l)
            return it;
        return intervals.insert({l,l-1}).first;
    }
    int merge(int l, int r) {
        auto it = start(l);
        int res = max(0, r - it->second);
        it->second = max(it->second, r);
        while(true) {
            auto nxt = next(it);
            if(nxt == end(intervals)) break;
            if(nxt->first > r + 1) break;
            res -= (min(it->second, nxt->second) - nxt->first + 1);
            it->second = max(it->second, nxt->second);
            intervals.erase(nxt);
        }
        return res;
    }
public:
    CountIntervals() {}

    void add(int left, int right) {
        c += merge(left, right);
    }

    int count() {
        return c;
    }
};

/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals* obj = new CountIntervals();
 * obj->add(left,right);
 * int param_2 = obj->count();
 */