[Java] Clean TreeMap | with Explanations | O(log n) Time
Idea\nIn add() function, use merge intervals approach and update the counter.\nIn this way, the count() function is O(1)\n\nTo merge intervals, we need to (1) s
### Idea\nIn `add()` function, use merge intervals approach and update the counter.\nIn this way, the `count()` function is `O(1)`\n\nTo merge intervals, we need to (1) search overlap intervals, (2) delete overlap intervals, and (3) add new interval.\n\nTherefore, **tree map** will be a good data structure here,\nbecause it (1) has sorted elements (2) can add/remove element in O(log n)\n\n### Steps of add()\n\n**Case 1: if no overlap**\n- just update the count, and add the interval to map\n\n**Case 2: overlap**\n1. define `new` as new interval(start, end)\n2. find the overlap interval (which is the right-most interval `cur` from map where `cur.end >= new.start`\n3. do merge:\n    count -= the count of interval `cur` \n\tremove interval `cur` from map\n    update the start, end of the internval `new`\n4. repeat 2-3 until there is no interval satisfy `cur.end >= new.start`\n5. count += the count of interval `new`\n6. add interval `new` to map\n\n### Solution v1\n```java\n// key, value => left, right\nTreeMap<Integer, Integer> m;\nint count = 0;\n\npublic CountIntervals() {\n    m = new TreeMap<>();\n}\n\npublic void add(int left, int right) {\n    if (m.floorKey(right) != null && m.get(m.floorKey(right)) < left) {\n        count += right - left + 1;\n        m.put(left, right);\n    } else {\n        int start = left, end = right;\n        while (m.floorKey(end) != null && m.get(m.floorKey(end)) >= left) {\n            int l = m.floorKey(end);\n            int r = m.get(l);\n            count -= r - l + 1;\n            m.remove(l);\n\n            start = Math.min(start, l);\n            end = Math.max(end, r);\n        }\n        count += end - start + 1;\n        m.put(start, end);\n    }\n}\n\npublic int count() {\n    return count;\n}\n```\n\n### Solution v2\nFor the case 1 & 2, they share the same logic. case 1 is redundant.\nTherefore, the `add()` could be improved to this:\n```java\npublic void add(int left, int right) {\n\tint start = left, end = right;\n\twhile (m.floorKey(end) != null && m.get(m.floorKey(end)) >= left) {\n\t\tint l = m.floorKey(end);\n\t\tint r = m.get(l);\n\t\tcount -= r - l + 1;\n\t\tm.remove(l);\n\n\t\tstart = Math.min(start, l);\n\t\tend = Math.max(end, r);\n\t}\n\tcount += end - start + 1;\n\tm.put(start, end);\n}\n```\n\n### Time complexity - Add(): `O(logn)`\nGiven there is `n` add operation. \nEach key in tree map is removed and added at most 1 respectively.\nThe time taken for `n` add() is `O(nlogn)`\nTherefore, the average time complexity for add() is `O(logn)`\n\n\n### Space complexity: `O(n)`\nThe max size of tree map is `n`\nTherefore, space = `O(n)`\n\n-------\nThe solution is based on [[Java] TreeMap w/ Explanation & Readability](https://leetcode.com/problems/count-integers-in-intervals/discuss/2039728/Java-TreeMap-w-Explanation-and-Readability). Credit to @wangdi814\n\nPlease upvote this if the explanation is helpful to you, thanks!\n\n\n
['Tree', 'Java']