[Python] SortedDict/SortedList & bisect_left with clear comments
SortedDict\n\npython\nfrom sortedcontainers import SortedDict\n\nclass CountIntervals(object):\n\n    def __init__(self):\n\t\t# { right -> left } sorted by key
**SortedDict**\n\n```python\nfrom sortedcontainers import SortedDict\n\nclass CountIntervals(object):\n\n    def __init__(self):\n\t\t# { right -> left } sorted by key (right end of the interval)\n        self.d = SortedDict()\n        # sum of all merged intervals == number of integers that are present in at least one interval.\n        self.cnt = 0 \n\n    def add(self, left, right):\n        """\n        :type left: int\n        :type right: int\n        :rtype: None\n        """\n        # Find the first interval whose key >= left, i.e. whose right end >= left\n        i = self.d.bisect_left(left)\n        # iterate all the intervals covered or partially covered by [left, right] \n        while i < len(self.d) and self.d.values()[i] <= right:\n            r, l = self.d.items()[i]\n            # Merge interval into a new larger interal:\n            left = min(left, l)\n            right = max(right, r)\n            # Subtracting the sum of merged smaller interval\n            self.cnt -= r - l + 1\n            # deleted the merged smaller interval from the SortedDict\n            self.d.popitem(i)\n        \n        # Adding by the sum of merged larger interval\n        self.cnt += right - left + 1\n        # Add the new merged interval \n        self.d[right] = left\n\n    def count(self):\n        """\n        :rtype: int\n        """\n        return self.cnt\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\n```\n\n`Time = log(N)`: each interval will be update (add/delete) once at most , so the amortized time complexity of `add` is O(logN), N is the number of time of `add` was called.\n`Space = O(N)`: SortedDict\n\n**SortedList**\nSame idea, just replace {right -> left} with the tuple (right, left)\n\n```python\nfrom sortedcontainers import SortedList\n\nclass CountIntervals:\n\n    def __init__(self):\n        self.cnt = 0 \n        self.intervals = SortedList()\n\n    def add(self, left, right):\n        k = self.intervals.bisect_left((left - 1, right))\n        while k < len(self.intervals) and self.intervals[k][1] <= right: \n            r, l = self.intervals.pop(k)\n            self.cnt -= r - l + 1\n            right = max(right, r)\n            left = min(left, l)\n            \n        self.cnt += right - left + 1\n        self.intervals.add((right, left))\n\n    def count(self):\n        return self.cnt\n\n```
['Python', 'Python3']