Watch 7 video solutions for Count Integers in Intervals, a hard level problem involving Design, Segment Tree, Ordered Set. This walkthrough by Coding Decoded has 2,700 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |