2276. Count Integers in Intervals - cocoder39/coco39_LC GitHub Wiki

2276. Count Integers in Intervals

from sortedcontainers import SortedList

class CountIntervals:

    def __init__(self):
        self.intervals = SortedList()
        self.counter = 0
        
    def add(self, left: int, right: int) -> None:
        idx = self.intervals.bisect_left((left, right)) # bisect_right also works
        
        while idx < len(self.intervals) and right >= self.intervals[idx][0]:
            l, r = self.intervals.pop(idx)
            self.counter -= r - l + 1
            right = max(right, r)
        
        if idx > 0 and left <= self.intervals[idx-1][1]:
            l, r = self.intervals.pop(idx-1)
            self.counter -= r - l + 1
            left = l
            right = max(right, r)
        self.intervals.add((left, right))
        self.counter += right - left + 1
        

    def count(self) -> int:
        return self.counter