[LeetCode] 352. Data Stream as Disjoint Intervals

 Problem : https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Use binary search to find the insertion point. Then merge the previous and next intervals.

class SummaryRanges:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.intervals = []

    def addNum(self, val: int) -> None:
        
        left, right = 0, len(self.intervals)
        
        while left < right:
            mid = left + (right -left) // 2
            
            tmp = self.intervals[mid]
            
            if tmp[0] <= val <= tmp[1]:
                return
            
            if tmp[0] > val:
                right = mid
            elif tmp[1] < val:
                left = mid + 1
        
        self.intervals.insert(left, [val, val])
        
        cur = self.intervals[left]
        pre = self.intervals[left-1] if left -1 >= 0 else None
        nxt = self.intervals[left+1] if left + 1 < len(self.intervals) else None
        
        if pre and pre[1] + 1 == cur[0]:
            pre[1] = cur[0]
            cur = pre
            self.intervals.pop(left)
            left -= 1
        
        if nxt and cur[1] + 1 == nxt[0]:
            cur[1] = nxt[1]
            self.intervals.pop(left + 1)
            

    def getIntervals(self) -> List[List[int]]:
            return self.intervals