2276. Count Integers in Intervals

Problem Link

Description

---

Given an empty set of intervals, implement a data structure that can:

• Add an interval to the set of intervals.
• Count the number of integers that are present in at least one interval.

Implement the CountIntervals class:

• CountIntervals() Initializes the object with an empty set of intervals.
• void add(int left, int right) Adds the interval [left, right] to the set of intervals.
• int count() Returns the number of integers that are present in at least one interval.

Note that an interval [left, right] denotes all the integers x where left <= x <= right.

 

Example 1:

Input
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]

Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals. 
countIntervals.add(2, 3);  // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count();    // return 6
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8);  // add [5, 8] to the set of intervals.
countIntervals.count();    // return 8
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 5 and 6 are present in the interval [5, 8].
                           // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
                           // the integers 9 and 10 are present in the interval [7, 10].

 

Constraints:

• 1 <= left <= right <= 109
• At most 105 calls in total will be made to add and count.
• At least one call will be made to count.

Solution

---

Python3

from sortedcontainers import SortedList
 
class CountIntervals:
 
    def __init__(self):
        self.sl = SortedList()
        self.res = 0
        
    def add(self, left: int, right: int) -> None:
        def overlap(l1, r1, l2, r2):
            lo = max(l1, l2)
            hi = min(r1, r2)
            
            return hi >= lo
 
        i = j = self.sl.bisect_left((left, -1))
        
        if i - 1 >= 0 and self.sl[i - 1][1] >= left:
            i -= 1
        
        while j < len(self.sl) and overlap(left, right, *self.sl[j]):
            j += 1
 
        for k in range(j - 1, i - 1, -1):
            L, R = self.sl[k]
            left = min(left, L)
            right = max(right, R)
            self.res -= R - L + 1
            del self.sl[k]
        
        self.res += right - left + 1
        self.sl.add((left, right))
 
    def count(self) -> int:
        return self.res
        
 
 
# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left,right)
# param_2 = obj.count()