Hard

Count Integers in Intervals

LAB

Apply add interval operations and return the count of unique integers covered after each operation.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      2,
      3
    ],
    [
      7,
      10
    ],
    [
      5,
      8
    ]
  ]
}

Output
[
  2,
  6,
  8
]

FUNCTION SHAPE

intervals: intMatrix→intArray

SOLUTION NOTE

Notice the similarities with insert interval. This is a hard problem that is instantly trivialized if you understand the insert interval problem carefully.

Reveal reference solution +

pythonREFERENCE

from sortedcontainers import SortedList
class CountIntervals:
    def __init__(self):
        self.res = 0
        self.intervals = SortedList()

    # looks like O(n + logn) time per add, BUT CONSIDER AMORTIZED ANALYSIS!!!
    # can only pop every added interval ONCE...
    # O(1 + logn) amortized for the binary search...
    def add(self, left: int, right: int) -> None:
        j = self.intervals.bisect_left((right+1, -inf)) - 1
        while j >= 0 and max(left, self.intervals[j][0]) <= min(right, self.intervals[j][1]):
            left = min(left, self.intervals[j][0])
            right = max(right, self.intervals[j][1])
            self.res -= self.intervals[j][1] - self.intervals[j][0] + 1
            self.intervals.pop(j)
            j -= 1
        self.intervals.add((left, right))
        self.res += right - left + 1

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

TimeO(log n) amortized per add

SpaceO(n)

Open on LeetCode ↗