# 2276. Count Integers in Intervals

## 题目

https://leetcode.com/problems/count-integers-in-intervals/

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
[[], [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`.

## 代码

``````class CountIntervals(object):

def __init__(self):
self.intervals = []
self.cnt = 0

"""
:type left: int
:type right: int
:rtype: None
"""
l, r = 0, len(self.intervals)
while l < r:
mid = l + (r - l) // 2
# 第一个i.right >= left的区间
if self.intervals[mid] < left:
l = mid + 1
else:
r = mid
if l >= len(self.intervals):
self.intervals.append((left, right))
self.cnt += right - left + 1
else:
i = l
while i < len(self.intervals) and self.intervals[i] <= right and self.intervals[i] >= left:
interval2 = self.intervals.pop(i)
self.cnt -= interval2 - interval2 + 1
left, right = min(left, interval2), max(right, interval2)
self.intervals.insert(i, (left, right))
self.cnt += right - left + 1

def count(self):
"""
:rtype: int
"""
return self.cnt``````

——此处是内容的分割线——