[Very Clean & Short C++] std::set
In short, we use a set (Self-Balancing BST) to manage the sorted intervals and keep track of count as we go.\nThe set will always contain DISJOINT, inclusive in
In short, we use a set (Self-Balancing BST) to manage the sorted intervals and keep track of count as we go.\nThe set will always contain DISJOINT, inclusive intervals.\nWhen we add, we insert a new interval into the set, and try to merge in both directions as far as we can.\n\n`count()` is `O(1)`\n\n`add()` has amortized complexity `O(N log N)`\nAlthough we may merge many intervals in a single call, once an interval has been merged, it\'s no longer in the set anymore. Therefore, each call to `add()` may introduce at most 1 new interval, and may merge (and remove) as many as have been added so far. An easy way to think of it is: in the worst case, every interval gets added a maximum of one time, and removed a maximum of one time. In other words, the number of deletions is bounded by the number of insertions.\n\n\n\n```cpp\n// https://leetcode.com/contest/weekly-contest-293/problems/count-integers-in-intervals/\nusing iv = pair<int,int>;\nusing IT = set<iv>::iterator;\n\nstruct CountIntervals {\n    int cnt = 0;  // track the current count\n    set<iv> ivals = { {-1,-1}, {INT_MAX,INT_MAX} };  // dummy values for edges\n    \n    template <class F>\n    pair<IT,bool> merge(IT it, F dir) {         // -> {resulting IT, keep going?}\n        auto [L,R] = *it;\n        auto cmp = dir(it, 1);                  // dir is prev() or next()\n        auto [x,y] = *cmp;\n\t\tbool intersectL = (L <= x && x <= R);  \n\t\tbool intersectR = (x <= L && L <= y);\n        if (intersectL || intersectR) {         // if `cmp` overlaps with `it`\n            cnt -= y-x+1;                       // remove contribution from cmp\n            ivals.erase(cmp);                   // erase both\n            ivals.erase(it); \n            iv q = { min(x, L), max(y, R) };    // merge into new, big interval\n            return ivals.insert(q);             // insert merged interval\n        }\n        return {it, false};  // otherwise, return it and indicate stop merging\n    }\n    void add(int L, int R) {\n        auto [it, go] = ivals.insert( {L,R} );\n        if (!go) return;\n        do {  tie(it,go) = merge(it, prev<IT>);  } while (go);  // merge left\n        do {  tie(it,go) = merge(it, next<IT>);  } while (go);  // merge right\n        tie(L, R) = *it;\n        cnt += R-L+1;\n    }\n    int count() { return cnt; }\n};\n```\n___\n___\n---\n\nFor reference, `set::insert()` returns a `pair<Iterator, bool>` of `{insertedIT, succeeded}`.\n\n`tie(...) = ` is "tuple assignment" in C++. For example,\n```cpp\nint a=1, b=2, c=3;\npair<int, int> p = {3,4};\ntie(a,c) = p;\nprintf("%d %d %d\\n", a, b, c);  // prints "3 2 4"\n```\n
[]