Python || merge intervals
We save non-overlapping intervals by two arrays, self.L and self.R. [self.L[i], self.R[i]] is the ith interval.\n2. When a new interval I = [left, right] is add
1. We save non-overlapping intervals by two arrays, `self.L` and `self.R`. `[self.L[i], self.R[i]]` is the `i`th interval.\n2. When a new interval `I = [left, right]` is added, use binary search to find:\n\t- `idx_l`: index of the first interval whose right endpoint >= `left`.\n\t- `idx_r`: index of the first interval whose left endpoint > `right` .\nHere are some examples:\n![image](https://assets.leetcode.com/users/images/1f6cfb34-b2b7-4b98-9963-249588b92a40_1680449623.203056.png)\n\t- case 1: `idx_l = 2, idx_r = 4`.\n\t- case 2: `idx_l = 1, idx_r = 4`.\n\t- case 3: `idx_l = 2, idx_r = 3`.\n3. From `idx_r-1` to `idx_l`, pop the interval one by one. Each time an interval is popped out, merge it with `I`.\n4. After all overlapping intervals are popped out, insert the merged `I`.\n```\nfrom bisect import bisect_left, bisect_right\n\nclass CountIntervals:\n    def __init__(self):\n        self.L = []\n        self.R = []\n        self.total = 0\n\n    def add(self, left: int, right: int) -> None:\n        if not self.L:\n            self.L.append(left)\n            self.R.append(right)\n            self.total += right-left+1\n        else:\n            idx_l, idx_r = bisect_left(self.R, left), bisect_right(self.L, right)\n            lm, rm = left, right\n            while idx_l < idx_r:\n                l1 = self.L.pop(idx_r-1)\n                r1 = self.R.pop(idx_r-1)\n                self.total -= r1-l1+1\n                lm = min(lm, l1)\n                rm = max(rm, r1)\n                idx_r -= 1\n            self.L.insert(idx_l, lm)\n            self.R.insert(idx_l, rm)\n            self.total += rm-lm+1\n        \n    def count(self) -> int:\n        return self.total
['Python3']