Python 3 - Merge Intervals
Intuition\n Describe your first thoughts on how to solve this problem. \nWe solve the problem by merging the intervals and keeping the count updated at the same
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe solve the problem by merging the intervals and keeping the count updated at the same time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWhen a new interval comes we check whether it can be merged with any other interval or not. If it merges with one interval or many, we do that by deleting the interval first while keeping the left and right boundary updated.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\u02C62)$$\nIn details the time complexity is O(n*(logN + N) + N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass CountIntervals:\n    def __init__(self):\n        self.intervals = []\n        self.cnt = 0\n\n    def add(self, left: int, right: int) -> None:\n        l,r = left,right\n\n        while True:\n            idx = bisect.bisect_left(self.intervals, (r, ))\n            if not len(self.intervals):\n                break\n            if (idx == 0 and self.intervals[idx][0] > right) or self.intervals[idx-1][1] < l:\n                break\n            \n            prev_l, prev_r = self.intervals[idx-1]\n            self.cnt -= (prev_r - prev_l + 1)\n            del self.intervals[idx - 1]\n\n            l = min(prev_l, l)\n            r = max(prev_r, r)\n        \n        self.intervals.insert(idx, (l,r))\n        self.cnt += (r - l + 1)\n\n    def count(self) -> int:\n        return self.cnt\n        \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# Your CountIntervals object will be instantiated and called as such:\n# obj = CountIntervals()\n# obj.add(left,right)\n# param_2 = obj.count()\n```
['Python3']