Python3  Sorted List | Merge Intervals in stream | FB follow-up for 56
Directly modified from my another post of solution: https://leetcode.com/problems/merge-intervals/discuss/1889983/python-binary-search-solution-for-fb-follow-up
Directly modified from my another post of solution: https://leetcode.com/problems/merge-intervals/discuss/1889983/python-binary-search-solution-for-fb-follow-up-merge-in-stream\n\n#### Original idea\nThis is the idea when I tried to come up with the solution for the follow-up question of 56 with out BST:\n\nThe basic idea of the solution is, when we merge intervals we are placing the points on a line segment. Let\'s denote start points as 0 and endpoints as 1 for separating different points, then we could get a representation. For instance, merged intervals: [1, 4], [7, 9], we could denote as\n[1,0], [4, 1], [7, 0], [9, 1]\n\nThen every time we have a new start and end, we could insert [st, 0], [ed, 1] to this list.\n\nThere are 2 key observations for this representations:\n\n1. we should not get 2 continous start or 2 continous end.\nFor instance, if after insert we get sth. like [1,0], [2, 0], [3, 1], [4,1], we know a merge should happens.\n\n2. If it is an insertion that will not trigger any merges, we could know that the place we insert start and end should differ only by 1.\nFor instance, we already have [1,0], [4,1] denotes the merged interval [1, 4] and we want to insert [5, 6] , we will get the index to insert is 2 and 3 which differs by 1\n\nBased on 1 and 2, let\'s denote the place to insert [st, 0] is idx1 and [ed, 1] is idx2, then:\n\n1. if idx2 - idx1 != 1, we know the elements between should be removed\n2. If we encounter invalid situation #1, we set idx1 = idx1 - 1 or idx2 = idx2 + 1 for further checks\n\n\n#### Update specified for this problem\nTo further modify for this question, we need to maintain a count variable and update it when new intervals come.\n\nWe added the number of [st, ed] for all new intervals to be added, and then remove the duplicates when we pop out the intervals that should cause duplicate additions.\n\n```Python\nfrom sortedcontainers import SortedList\nclass CountIntervals:\n\n    def __init__(self):\n        self.sorted_list = SortedList()\n        self.num = 0\n\n    def add(self, st: int, ed: int) -> None:\n        self.sorted_list.add([st, 0])\n        self.sorted_list.add([ed, 1])\n        \n        self.num += ed - st + 1\n        # print(self.sorted_list)\n        \n        idx1 = self.sorted_list.index([st, 0])\n        idx2 = self.sorted_list.index([ed, 1])\n        \n     \n        if idx1 - 1 >= 0 and self.sorted_list[idx1 - 1][1] == 0:\n            idx1 -= 1\n        if idx2 + 1 < len(self.sorted_list) and self.sorted_list[idx2 + 1][1] == 1:\n            idx2 += 1\n        \n        if idx2 - idx1 != 1:\n            j = idx1 + 1\n            for _ in range(idx1 + 1, idx2):\n                if self.sorted_list[j][1] == 0: # encounter a start point need to be remove\n                    self.num -= (self.sorted_list[j + 1][0] - self.sorted_list[j][0] + 1) # so we need to decrease the duplicated addition to the total number\n                self.sorted_list.pop(j)\n\n    def count(self) -> int: # O(1)\n        return self.num\n```
['Python3']