Python Binary Search
Approach\n1. If there is no intervals yet, just add it and keep track of the count. Otherwise:\n2. Search through intervals for where left of the new interval i
**Approach**\n1. If there is no intervals yet, just add it and keep track of the count. Otherwise:\n2. Search through intervals for where left of the new interval is less than the end of any interval.\n3. Search through intervals for where right of the new interval is greater than the start of any interval.\n4. If our found left index is inside an interval, take the minimum of it and the interval.\n5. If our found right index is inside of an interval, take hte maximum of it and the interval.\n6. Otherwise [left, right] will be inserted into the list. \n7. Keep track of counts as we go, we\'re going to add to counts the amount of the new interval\n8. We\'re going to remove from counts all intervals between our left index and right index. If we\'re just inserting, the space between left index and right index will be 0. So we\'ll only be adding.\n\n**Other Considerations**\nIn the competition two things caused my time limit exceeded:\n1. Not keeping track of counts and walking it instead. One of the test cases is, add add add... for 50+ iterations followed by count count count... for 100+ iterations. So if you have to walk count each time, you\'ll TLE.\n2. Even with that, updating the interval list afterwards with array slicing. This is confusing for me.\n\nHad to look at yag313\'s solution to see array slice + assignment which is much much faster. I think python does extra memory allocation and will add two arrays together followed by another addition of the third array in my naive attempt.\n\n***Would love a detailed explanation from anyone on what the time complexity between the two lines are please.***\n\n```\nimport bisect\nfrom operator import itemgetter\n\nclass CountIntervals:\n\n    def __init__(self):\n        self.intervals = []\n        self.cur_count = 0\n\n    def add(self, left: int, right: int) -> None:\n        if not self.intervals:\n            self.intervals.append([left, right])\n            self.cur_count = right - left + 1\n            return\n\n        l = bisect.bisect_left(self.intervals, left, key=itemgetter(1))\n        r = bisect.bisect_right(self.intervals, right, key=itemgetter(0))\n        \n        if l < len(self.intervals):\n            left = min(left, self.intervals[l][0])\n            \n        if r > 0:\n            right = max(right, self.intervals[r-1][1])\n        \n        to_add = right - left + 1\n        \n        to_remove = 0\n        for i in range(l, r):\n            to_remove += self.intervals[i][1] - self.intervals[i][0] + 1\n            \n        self.cur_count += to_add - to_remove\n        \n        # TOO SLOW!!\n        # 15 seconds!!\n        # self.intervals = self.intervals[:l] + [[left, right]] + self.intervals[r:]\n        \n        # 1.3 - 1.6 seconds\n        self.intervals[l:r] = [[left, right]]\n\n    def count(self) -> int:\n        return self.cur_count\n\n\n# Your CountIntervals object will be instantiated and called as such:\n# obj = CountIntervals()\n# obj.add(left,right)\n# param_2 = obj.count()\n```
['Binary Tree', 'Python', 'Python3']