Java | TreeSet O(NlogN) add, O(1) count
This question is similar to Range module\n Maintain a list of sorted non-overlapping intervals in a TreeSet\n When adding an interval [left, right] find the set
* This question is similar to [Range module](https://leetcode.com/problems/range-module/)\n* Maintain a list of sorted non-overlapping intervals in a TreeSet\n* When adding an interval [left, right] find the set of all intervals that may potentially overlap. Merge any overlapping intervals with the interval to be added\n* While performing merge, keep track of # of integers that have been removed or added. This makes `count()` O(1) and avoids needing to go through the entire TreeSet when `count()` is called which avoids TLE for large test cases.\n* Time complexity: O(NlogN). log N to find the first overlapping interval, then O(N) worst case to get the set of overlapping intervals. In the worse case, each interval could overlap with the current interval. So we remove N intervals in the worst case. TreeSet `remove()` is logN for each interval.\n* Space complexity: O(N)\n\n```\n    TreeSet<Interval> intervals;\n    int count;\n    \n    public CountIntervals() {\n        intervals = new TreeSet<>(new Comparator<Interval>() {\n           public int compare(Interval left, Interval right) {\n               if (left.right == right.right) {\n                   return left.left - right.left;\n               }\n               return left.right - right.right;\n           } \n        });\n    }\n    \n    public void add(int left, int right) {\n        Interval searchInterval = new Interval(left - 1, left - 1); // Handles edge case for overlapping intervals like [5, 10], [10, 12]\n        int start = left;\n        int end = right;\n        Iterator<Interval> itr = intervals.tailSet(searchInterval).iterator();\n        while (itr.hasNext()) {\n            Interval current = itr.next();\n            if (left <= current.right && right >= current.left) {\n                start = Math.min(start, current.left);\n                end = Math.max(end, current.right);\n                count -= current.right - current.left + 1;   // Update count inline and avoid TLE\n                itr.remove();\n            } else {\n                break;\n            }\n        }\n        intervals.add(new Interval(start, end));\n        count += end - start + 1;   // Update count inline and avoid TLE\n    }\n    \n    public int count() {      \n        return count;\n    }\n```
[]