#2276

Count Integers in Intervals

master · 1830 · lc hard +32 · 35.8% accepted · 621 likes · top 14%

Description

Starting with no intervals, implement a data structure that supports:

- Adding a new interval.

- Counting distinct integers covered by at least one stored interval.

Implement the CountIntervals class:

- CountIntervals() Initializes the object with no intervals.

- void add(int left, int right) Adds [left, right] to the stored intervals.

- int count() Returns the total count of integers in at least one interval.

An interval [left, right] covers every integer 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]

Example 2:

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].

Code

class CountIntervals:

    def __init__(self):
        

    def add(self, left: int, right: int) -> None:
        

    def count(self) -> int:
        


# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left,right)
# param_2 = obj.count()

class CountIntervals:

    def __init__(self):
        

    def add(self, left: int, right: int) -> None:
        

    def count(self) -> int:
        


# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left,right)
# param_2 = obj.count()