Given an empty set of intervals, implement a data structure that can:
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 <= 109105 calls in total will be made to add and count.count.#2276 Count Integers in Intervals is a design problem where you must maintain a dynamic set of integer ranges and efficiently return how many unique integers are covered. The main challenge is handling overlapping intervals without double counting.
A common approach uses an ordered map / ordered set to store disjoint intervals. When adding a new interval [left, right], you locate overlapping intervals, merge them, and update a running total of covered integers. This ensures the structure always keeps non‑overlapping ranges while supporting fast lookups and merges.
Another advanced option is a segment tree with lazy propagation across the range [1, 1e9]. Nodes represent covered segments, and updates mark ranges as covered while maintaining counts. Although heavier to implement, this structure efficiently supports large coordinate ranges.
Both strategies rely on merging intervals or marking coverage while maintaining a global count of unique integers. Balanced tree operations typically give O(log n) updates with efficient interval merging.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Ordered Map / Interval Merging | O(log n) average per add (may merge multiple intervals) | O(n) |
| Segment Tree with Lazy Propagation | O(log R) per update where R is the value range | O(R) implicit tree nodes |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
How can you efficiently add intervals to the set of intervals? Can a data structure like a Binary Search Tree help?
How can you ensure that the intervals present in the set are non-overlapping? Try merging the overlapping intervals whenever a new interval is added.
How can you update the count of integers present in at least one interval when a new interval is added to the set?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving interval merging, ordered sets, and segment trees frequently appear in FAANG-style interviews. This problem tests data structure design, range management, and efficient updates over large domains.
Merging intervals ensures the data structure only stores disjoint ranges. This prevents double counting of integers when intervals overlap and allows the total covered count to be updated accurately and efficiently.
An ordered map (such as TreeMap or C++ map) storing non-overlapping intervals works well for this problem. It allows efficient searching of neighboring intervals and merging overlaps. A segment tree with lazy propagation is another option when dealing with very large ranges.
The most common optimal solution maintains disjoint intervals using an ordered map or balanced tree. When adding a new interval, overlapping intervals are merged and the total count of covered integers is updated. This avoids double counting and keeps operations efficient.