2276. Count Integers in Intervals LeetCode Solution
In this guide, you will get 2276. Count Integers in Intervals LeetCode Solution with the best time and space complexity. The solution to Count Integers in Intervals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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].
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.
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(n)
2276. Count Integers in Intervals LeetCode Solution in C++
class CountIntervals {
public:
void add(int left, int right) {
while (isOverlapped(left, right)) {
auto it = prev(intervals.upper_bound(right));
const int l = it->first;
const int r = it->second;
left = min(left, l);
right = max(right, r);
intervals.erase(l);
cnt -= r - l + 1;
}
intervals[left] = right;
cnt += right - left + 1;
}
int count() {
return cnt;
}
private:
map<int, int> intervals;
int cnt = 0;
bool isOverlapped(int left, int right) {
auto it = intervals.upper_bound(right);
return it != intervals.begin() && prev(it)->second >= left;
}
}; /* code provided by PROGIEZ */
2276. Count Integers in Intervals LeetCode Solution in Java
class CountIntervals {
public void add(int left, int right) {
while (isOverlapped(left, right)) {
final int l = intervals.floorKey(right);
final int r = intervals.get(l);
left = Math.min(left, l);
right = Math.max(right, r);
intervals.remove(l);
count -= r - l + 1;
}
intervals.put(left, right);
count += right - left + 1;
}
public int count() {
return count;
}
private TreeMap<Integer, Integer> intervals = new TreeMap<>();
private int count = 0;
private boolean isOverlapped(int left, int right) {
// L := the maximum number <= end
Integer l = intervals.floorKey(right);
return l != null && intervals.get(l) >= left;
}
} // code provided by PROGIEZ
2276. Count Integers in Intervals LeetCode Solution in Python
from sortedcontainers import SortedDict
class CountIntervals:
def __init__(self):
self.intervals = SortedDict()
self.cnt = 0
def add(self, left: int, right: int) -> None:
while self._isOverlapped(left, right):
i = self.intervals.bisect_right(right) - 1
l, r = self.intervals.popitem(i)
left = min(left, l)
right = max(right, r)
self.cnt -= r - l + 1
self.intervals[left] = right
self.cnt += right - left + 1
def count(self) -> int:
return self.cnt
def _isOverlapped(self, left: int, right: int) -> bool:
i = self.intervals.bisect_right(right)
return i > 0 and self.intervals.peekitem(i - 1)[1] >= left # code by PROGIEZ
