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.Problem Overview: Design a data structure that supports two operations: add(left, right) to insert an interval and count() to return how many distinct integers are covered by all inserted intervals. Intervals can overlap, so the main challenge is maintaining the total number of unique integers without double-counting overlaps.
Approach 1: Interval Merging using Sorted List (O(n) add, O(1) count)
Store all disjoint intervals in a sorted list ordered by start value. When you call add(left, right), iterate through the list and merge any intervals that overlap with the new one. During merging, subtract the lengths of removed intervals from the running total and add the merged interval length back. The count() operation simply returns the maintained total. Each insertion may scan and merge multiple intervals, giving O(n) time for add and O(1) time for count, with O(n) space for stored intervals. This approach works well in Python or C++ using lists and binary search.
Approach 2: Balanced Tree (Ordered Set) (O(log n) add, O(1) count)
Use a balanced BST or ordered map keyed by interval start. For each add(left, right), locate the first overlapping interval using a tree search, then repeatedly merge all overlapping neighbors while updating the total covered count. Because the tree keeps intervals sorted automatically, locating and removing overlaps takes O(log n) per structural operation. The total count is tracked incrementally, so count() remains O(1). Space complexity is O(n). Languages like Java (TreeMap) and JavaScript (ordered structures) implement this cleanly. This solution models a classic Ordered Set design problem.
Although the problem tags also reference Segment Tree, a full segment tree across the range up to 109 is usually unnecessary unless you implement coordinate compression. Maintaining merged intervals in a tree is simpler and achieves the required efficiency.
Recommended for interviews: The balanced tree solution is typically expected. It shows you understand interval merging, ordered structures, and incremental counting. Starting with the sorted-interval merging idea demonstrates strong reasoning, while implementing it with a tree highlights practical design skills for dynamic data structures.
Maintain a sorted list of non-overlapping intervals. When a new interval is added, merge it with existing overlapping or adjacent intervals. This allows efficient counting since each interval contributes exactly its length to the total count.
The constructor initializes an empty list to store intervals. When adding a new interval, it is appended to the list, and the list is sorted to ensure order. Overlapping intervals in the sorted list are then merged. Counting simply involves summing the lengths of all intervals.
Time Complexity: O(n log n) for sorting intervals during add operations.
Space Complexity: O(n) for storing intervals.
This approach uses a self-balancing binary search tree or an ordered set to store and manage intervals. Using such data structures makes merging dynamic intervals efficient.
In this Java solution, a TreeMap is used to map the start of each interval to its end. This enables efficient lookup and merging of intervals when a new interval overlaps with existing ones. The total count of distinct integers is maintained and adjusted with each addition.
Java
JavaScript
Time Complexity: O(log n) for adding intervals and counting, where n is the number of intervals stored.
Space Complexity: O(n) for storing intervals.
According to the problem description, we need to maintain a set of intervals that supports adding intervals and querying operations. For adding intervals, we can use a segment tree to maintain the interval set.
The segment tree divides the entire interval into multiple non-contiguous sub-intervals, with the number of sub-intervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we need to use lazy propagation to ensure efficiency.
[1, N];[x, x];[l, r], its left child is [l, mid] and its right child is [mid+1, r], where mid = \lfloor (l + r) / 2 \rfloor (i.e., floor division).Since the data range in the problem is large, we can use a dynamically opened segment tree. A dynamically opened segment tree means that we only open nodes when needed, rather than opening all nodes at the beginning, which saves space.
In terms of time complexity, each operation has a time complexity of O(log n). The space complexity is O(m times log n), where m is the number of operations and n is the data range.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Interval Merging using Sorted List | Time Complexity: O(n log n) for sorting intervals during add operations. |
| Approach 2: Using Balanced Tree (Ordered Set) | Time Complexity: O(log n) for adding intervals and counting, where n is the number of intervals stored. |
| Segment Tree (Dynamic Opening) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Interval Merging with Sorted List | O(n) per add, O(1) count | O(n) | Simple implementation when number of intervals is moderate |
| Balanced Tree / Ordered Set | O(log n) add, O(1) count | O(n) | Best general solution for frequent updates and large interval sets |
Count Integers in Intervals | Leetcode 2276 | Easy TreeMap | Live coding session • Coding Decoded • 2,700 views views
Watch 6 more video solutions →Practice Count Integers in Intervals with our built-in code editor and test cases.
Practice on FleetCode