Java TreeMap, easy to explain and memorize in interview (with pictures)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nUse TreeMap (Balanced Binary Search Tree) to track every interval, and maintain order
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nUse TreeMap (Balanced Binary Search Tree) to track every interval, and maintain order.\n\nWhen "add(left, right)" causes overlap with existing intervals, remove every interval "covered" by [left,right], and add [left,right] into the TreeMap.\n\nI am trying to make code as memorizable and easy to understand as possible.\n\nThere are many cases in this problem.\n- Overlap between existing and new intervals\n- The new interval just overlaps (but does not totally cover) some existing intervals.\n\n\nConverge some cases to some easily-explainable steps, **easy to explain in interview**.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nIn some solutions, in TreeMap, key is left edge, value is right edge of interval. Then there are many corner cases.\nIn my solution, in TreeMap, key is edge of interval (either left or right), value is Boolean (false means left edge, true means right edge).\n\n```\nTreeMap<Integer, Boolean> edges;\n\n// true -- right edge\n// false -- left edge\n// If add(3,5), then the map has (3,false), (6,true)\n// range [3,6) -- left included, right not included\n\n// Use "Example 1" in the description\n// ["CountIntervals", "add", "add", "count", "add", "count"]\n// [[], [2, 3], [7, 10], [], [5, 8], []]\n// 1. add 2,3\n// edges: (2,false), (4,true)\n// 2. add 7,10\n// edges: (2,false), (4,true), (7,false), (11, true)\n// 3. add 5,8 -- handle overlap\n// edges: (2,false), (4,true), (5,false), (11, true)\n```\n\nHow to handle overlap?\n\n## Step 1\n![code1.jpg](https://assets.leetcode.com/users/images/378188b2-5d0d-457b-9ca8-111bb624043d_1677472560.4769201.jpeg)\nIn this picture,\n- If `left` is inside one existing interval, **extend** `left` to the left edge of the interval.\n- If `right` is inside one existing interval, same, **extend** `right` to the right edge of the interval.\nThen every interval which overlaps with `[left,right]` is **totally covered** by `[left,right]` now.\n\n![code2.jpg](https://assets.leetcode.com/users/images/c466c59a-3677-47df-ae8e-e2f7cf4ac02a_1677473888.111718.jpeg)\n\n## Step 2\nRemove every interval covered by `[left,right]` from TreeMap, also update `count0` (see in code).\n\n## Step 3\nAdd interval `[left,right]` to TreeMap, and also update `count0`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`void add(left,right)` is amortized $$O(log(n))$$\n`int count()` is $$O(1)$$\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.SortedMap;\n\nclass CountIntervals {\n\n    TreeMap<Integer, Boolean> edges;\n    int count0 = 0;\n\n    public CountIntervals() {\n        edges = new TreeMap<>();\n    }\n    \n    public void add(int left, int right) {\n        ++right; // right not included\n\n        // $left can be inside one existing interval\n        // Extend $left!\n        Integer a = edges.floorKey(left);\n        if (a!=null) {\n            if (!edges.get(a)) {\n                // left edge\n                left = a;\n            } else {\n                // right edge\n                if (left == a) {\n                    left = edges.lowerKey(a);\n                }\n            }\n        }\n\n        // $right can be inside one existing interval\n        // Extend $right!\n        Integer b = edges.ceilingKey(right);\n        if (b!=null) {\n            if (edges.get(b)) {\n                // right edge\n                right = b;\n            } else {\n                // left edge\n                if (right == b) {\n                    right = edges.higherKey(b);\n                }\n            }\n        }\n\n        // remove everything between a, b (include a,b)\n        SortedMap<Integer, Boolean> submap = \n            edges.headMap(right,true).tailMap(left,true);\n\n        int curr = -12345;\n        for (Map.Entry<Integer, Boolean> e : submap.entrySet()) {\n            if (e.getValue()) {\n                count0 -= (e.getKey()-curr);\n            } else {\n                curr = e.getKey();\n            }\n        }\n        submap.clear();\n\n        // Insert this interval\n        edges.put(left, false);\n        edges.put(right, true);\n        count0 += (right-left);\n    }\n    \n    public int count() {\n        return count0;\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```
['Tree', 'Binary Search Tree', 'Java']