304 North Cardinal St.
Dorchester Center, MA 02124

# Count Integers in Intervals LeetCode Solution

## Problem – Count Integers in Intervals LeetCode Solution

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

### Count Integers in Intervals LeetCode Solution in C++

``````class CountIntervals {
public:
map<int, int> m;
int cnt = 0;
void add(int left, int right) {
auto it = m.upper_bound(left);
if (it != begin(m) && prev(it)->second >= left)
it = prev(it);
for (; it != end(m) && it->first <= right; m.erase(it++)) {
left = min(left, it->first);
right = max(right, it->second);
cnt -= it->second - it->first + 1;
}
cnt += right - left + 1;
m[left] = right;
}
int count() { return cnt; }
};
``````

### Count Integers in Intervals LeetCode Solution in Java

``````class CountIntervals {
TreeMap<Integer, Integer> m = new TreeMap<>();
int cnt = 0;
public void add(int left, int right) {
var it = m.floorEntry(left);
if (it == null || it.getValue() < left)
it = m.higherEntry(left);
for (; it != null && it.getKey() <= right; it = m.higherEntry(left)) {
left = Math.min(left, it.getKey());
right = Math.max(right, it.getValue());
cnt -= it.getValue() - it.getKey() + 1;
m.remove(it.getKey());
}
m.put(left, right);
cnt += right - left + 1;
}
public int count() { return cnt; }
}
``````

### Count Integers in Intervals LeetCode Solution in Python

``````from sortedcontainers import SortedList

class CountIntervals:

def __init__(self):
self.cnt = 0
self.intervals = SortedList()

def add(self, left: int, right: int) -> None:
k = self.intervals.bisect_left((left, right))
while k < len(self.intervals) and self.intervals[k] <= right:
l, r = self.intervals.pop(k)
self.cnt -= r - l + 1
right = max(right, r)
if k and left <= self.intervals[k-1]:
l, r = self.intervals.pop(k-1)
self.cnt -= r - l + 1
left = l
right = max(right, r)
self.cnt += right - left + 1

def count(self) -> int:
return self.cnt
``````
##### Count Integers in Intervals LeetCode Solution Review:

In our experience, we suggest you solve this Count Integers in Intervals LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Find the Count Integers in Intervals LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Find the Count Integers in Intervals LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions