Python | Merge Intervals without binary search | Faster than 100%
My basic idea is using a dictionary to represent the left and right boundary of intervals. \n1. Insert keys into map.\n\tif we add intervals [2, 3], [7, 10], [5
My basic idea is using a dictionary to represent the left and right boundary of intervals. \n1. Insert keys into map.\n\tif we add intervals [2, 3], [7, 10], [5, 8], the dict `boundary_cnt` will be  {2: 1, 4: -1, 5: 1, 7: 1, 9: -1,11: -1} (the value is sorted)\n2. Go through the intervals and count.\n\tUse `cur_sum` to decide if we reach the left boundary or right boundary of an interval. Initailize the left boundary with -1. `cur_sum += boundary_cnt[v]` , if `cur_sum > 0`, v must be in the interval. if `cur_sum == 0`, v is the right boundary of the interval. \nFor example, \nv = 2, cur_sum = 1, since `left` = -1, v = 2 is the left boundary of interval\nv = 4, cur_sum = 0, v = 4 is right most one. The length of this interval is 2. Then we re-initialize the `left`\nv = 5, cur_sum = 1, find a new `left`\nv = 7, cur_sum = 2, it\'s not the left nor right, we can delete the key \nv = 9, cur_sum = 1, same as above\nv = 11, cur_sum = 0, finally find the `right`.  The length of this interval is 6, total count is 8. In the meanwhile, since we delete some keys between (5, 11), to make sure we can still find the paired left and right next time, update the value of `boundary_cnt[11]`\n\n\n```\nclass CountIntervals:\n\n    def __init__(self):\n        self.boundary_cnt = defaultdict(int)\n        self.cur_res = -1\n        \n    def add(self, left: int, right: int) -> None:\n        self.boundary_cnt[left] += 1\n        self.boundary_cnt[right + 1] -= 1\n        self.cur_res = -1\n        \n    def count(self) -> int:\n        if not self.boundary_cnt:\n            return 0\n        if self.cur_res != -1:\n            return self.cur_res\n        \n        res = 0\n        values = sorted(self.boundary_cnt.keys())\n        left = -1\n        cur_sum = 0\n\n        for v in values:\n            if v not in self.boundary_cnt:\n                continue\n            \n            cur_sum += self.boundary_cnt[v]\n            if left == -1:\n                if cur_sum > 0:\n                    left = v\n                continue\n                \n            if cur_sum > 0:\n                del self.boundary_cnt[v]\n            else:\n                right = v\n                res += right - left \n                self.boundary_cnt[v] = - self.boundary_cnt[left]\n                left = -1\n\n        self.cur_res = res\n        return res\n```
['Python']