Merge Intervals in TreeMap (start->end)
Intuition\nWe can calculate count of integers (size of interval) during add operation. So, let\'s keep all not overlapping intervals and merge it with new inter
# Intuition\nWe can calculate count of integers (size of interval) during `add` operation. So, let\'s keep all not overlapping intervals and merge it with new interval in the `add` operation.\nFor proper `count`calculation duting `merger` interval we do the following:\n`count -= size (existing interval)` and then `count += size(merged interval)`.\n\nThe most tricky part is to keep intevals in `TreeMap` for quick access by start interval and calculating overlaps because new interval may overlap from `0` to `n` interval from left, rigth and in the midle of `left` and `right` parameters of `add` method.\n\n# Approach\nRemove all intevals from left for new inteval and merge.\nRemove all interval from right for new interval and merge.\n\nPut merged inteval to the collection.\n\n# Complexity\n- Time complexity: `avg O(logn)`, `O(nlogn)` in the worst case becase we have to remove all `n-1` intervals in case of adding inteval that overlap all existing.\n- Space complexity: `O(n)` in the forst case\n\n# Code\n```\nclass CountIntervals {\n    private int count;\n    private final TreeMap<Integer, Integer> ranges = new TreeMap<>();\n\n    public CountIntervals() {}\n    \n    public void add(int left, int right) {\n        if (isFullContains(left, right)) return;\n\n        var leftEntry = ranges.floorEntry(left);\n        while (leftEntry != null && leftEntry.getValue() >= left) {\n            removeByStart(leftEntry.getKey());\n            \n            left = Math.min(left, leftEntry.getKey());\n            right = Math.max(right, leftEntry.getValue());\n            \n            leftEntry = ranges.floorEntry(left);\n        }\n        \n        var rightEntry = ranges.ceilingEntry(left);\n        while (rightEntry != null && rightEntry.getKey() <= right) {    \n            removeByStart(rightEntry.getKey());\n\n            left = Math.min(left, rightEntry.getKey());\n            right = Math.max(right, rightEntry.getValue());\n\n            rightEntry = ranges.ceilingEntry(left);\n        }\n\n        ranges.put(left, right);\n        count += size(left, right);\n    }\n    \n    public int count() {\n        return count;\n    }\n\n    private boolean isFullContains(int left, int right) {\n        var leftEntry = ranges.floorEntry(left);\n        return leftEntry != null && right <= leftEntry.getValue();\n    }\n\n    private void removeByStart(int start) {\n        int end = ranges.remove(start);\n        count -= size(start, end);\n    }\n\n    private static int size(int a, int b) {\n        return b - a + 1;\n    }\n}\n\n/**\n * Your CountIntervals object will be instantiated and called as such:\n * CountIntervals obj = new CountIntervals();\n * obj.add(left,right);\n * int param_2 = obj.count();\n */\n```
['Ordered Map', 'Java']