Tree of Merged Intervals - Thorough Explaination
Thought Process:\n\nWhat are the possibilities when inserting a new interval?\n\n1. The new interval partly intersects with existing intervals. \n\t- Ex: [1, 2]
**Thought Process:**\n\n*What are the possibilities when inserting a new interval?*\n\n1. The new interval partly intersects with existing intervals. \n\t- Ex: [1, 2] partly intersects with [2, 3]\n\t- This pair can be merged as [1,3] and the existing interval of [2,3] can be removed.\n2. The new interval is encapsualted by an existing interval. \n\t- Ex: [2,3] is encapsulated by [1,4]\n\t- In this case, there is no need to add any interval.\n3. The new interval does not intersect with any existing intervals.\n\t- Ex: [1,2] does not intersect with [3,4]\n\t- [1,2] can simply be added as the new interval\n\n*Which operations do we want to perform on the intervals?*\n\n1. Inserting a new interval seems critical.\n3. Searching for existing intervals that partly intersects or encapsulates a new interval.\n2. Deleting intervals when some may intersect and need to be merged.\n3. Maintaining the count of the unique integers between all intervals.\n\n*Which data structures can be used to store intervals, and which one is best? Keep in mind that each operation will be run N times.*\n\n1. List of Intervals: This data structure takes O(N) time to insert/delete/search an interval. When these operations are run N times each, the total Time Complexity is O(N^2) and will most likely TLE.\n\t- This may be the first idea borrowed from Merge Intervals, but is too inefficient.\n\n2. Balanced Binary Search Tree of Intervals: This data structure is far more ideal since it can insert/search/delete an interval in log(N). When applied to N operations the final Time Complexity is O(Nlog(N)).\n\t- This is the optimal runtime for searching and delete. Implementing such a self-balancing Tree from scratch would be quite tedious, so let\'s use a TreeMap.\n\t- TreeMaps operate as HashMaps with key/val pairs, but the operations do not run in O(1). The upside is that entries are sorted by key, allowing for in-order successor and pre-order predecessors to be looked up.\n\n*How should this Tree be used to insert/search/delete for new intervals, and resolve encapusalations + intersections?*\n\n1. The Tree can be represented by nodes, where each node holds the [left, right] of its interval.\n\t- For any node, all nodes the left must have a smaller [**left**, right], while all nodes on the right must have a greater [**left**, right]. This makes the BST property simple to allow for searching.\n\n2. For any new intervals, let\'s check for an intersection on the left side or encapsulation.\n\t- Example:  existingIntervals = [[1,5], [6, 9]] | newInterval = [7, 11]\n\t- Clearly [6, 9] & [7, 11] intersect.\n\t\n\ta) From the root of the tree, search for an existing interval with a left value **less than or equal** to the new interval\'s left.\n\t\t\n\t- There may be many such intervals, so which one is most likely to intersect with the new interval? That would be the existing interval with the **greatest** left value. This is known as the pre-order predecessor, resulting in finding [6, 9].\n\t- To check if they intersect, simply check ```node.right >=  left``` meaning 9 > 7 from above example. In this case the ```left = 7``` should be updated to the existing node\'s left so ```left = 6```.\n\t- For encapsulation, it is possible that ```node.right >=  right``` meaning the existing interval goes past the new interval\'s right bounds. And the existing interval has a left value going below the new interval\'s left bounds. In this case, no interval needs to be added.\n\n3. *How should intervals on the right side be checked?*\n\t- Example:  existingIntervals = [[6, 9], [10,11]] | newInterval = [2, 11]\n\t- Clearly [2,11] intersects with [6, 9], [10,11] thru the right side .\n\t\n\ta) From the root of the tree, search for an existing interval with a left value **greater than or equal** to the new interval\'s left.\n\t\t\n\t- There may be many such intervals, so which one is most likely to intersect with the new interval? That would be the existing interval with the **smallest** left value. This is known as the in-order successor, resulting in finding [6, 9].\n\t- To check if they intersect, simply check ```node.right <=  right``` meaning 9 <= 11  from above example. The Tree is only sorted by left values, so it is not clear which right is greate. Will update the right value based on whichever is greater ```right = max(right, node.right);```\n\t- In the above example, the intersections on the right side are not completely handled by finding just 1 intersecting interval. Hence, we need a loop to find the reamining right side intersection so long as the condition ```node.right <=  right``` holds true.\n\n\n4. The hard work is done, but how can count be maintained?\n\t- Initially assume the new interval size is ```intervalSize = right - left + 1```\n\t- If an encapsulation is found, there are no new numbers in our data structure.\n\t- If an intersection is found, simply decrement ```intervalSize``` based on the shared intersecting numbers.\n\t- Finally, add the updated ```intervalSize``` to the global counter variable.\n```\nclass CountIntervals {\n    \n    TreeMap<Integer, Integer> intervals = new TreeMap();\n    int existingNumbers = 0;\n\n    public void add(int left, int right) {\n        // Get number count in interval\n        int intervalSize = right - left + 1;\n        \n        // Check for left intersection\n        Map.Entry<Integer, Integer> leftEntry = intervals.floorEntry(left);\n        if (leftEntry != null) {\n            // Parse potentially intersecting interval\n            int newLeft = leftEntry.getKey(), newRight = leftEntry.getValue();\n\n            // Check if left side encapsualtes new interval\n            if (newRight >= right)\n                return;\n\n            // Check if left side intersects new interval\n            if (newRight >= left) {\n                // Subtract intersecting/uduplicate numbers\n                intervalSize -= newRight - left + 1; // Count numbers deleted/intersected\n                \n                // Delete intersecting interval\n                intervals.remove(newLeft);\n                \n                // Update left to merge as smaller value\n                left = newLeft;\n            }\n        }\n        \n        // Check for right intersection\n        Map.Entry<Integer, Integer> rightEntry = intervals.ceilingEntry(left);\n        while (rightEntry != null && rightEntry.getKey() <= right) {\n            // Parse intersecting interval\n            int newLeft = rightEntry.getKey(), newRight = rightEntry.getValue();\n            \n            // Subtract intersecting/duplicate numbers\n            intervalSize -= Math.min(right, newRight) - newLeft + 1;\n            \n            // Delete intersecting interval\n            intervals.remove(newLeft);\n            \n            // Update right to merge as greater value\n            right = Math.max(right, newRight);\n            \n            // Check for another intersection\n            rightEntry = intervals.ceilingEntry(left);\n        }\n        \n        // Add new numbers and insert interval\n        existingNumbers += intervalSize;\n        intervals.put(left, right);\n    }\n    \n    public int count() {\n        return existingNumbers;\n    }\n}
['Tree', 'Java']