Count Integers in Intervals
Asked at Databricks
Problem
Design a data structure that counts the number of integers currently covered by at least one added interval. Implement the CountIntervals class with methods: add(left, right) adds the interval [left, right], and count() returns the total number of unique integers covered.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Hard | View all Databricks questions → |
How to Think About It
Brute force: use a boolean array to mark covered positions. add() marks positions, count() sums the array. Time O(n) per add where n is interval length. Too slow for large ranges.
Key insight: maintain a sorted list of disjoint intervals. When adding a new interval, merge all overlapping intervals. The total covered count is the sum of (right - left + 1) for each interval.
Use a TreeMap (Java) or sorted list of intervals. For add(left, right), find all intervals that overlap with [left, right], remove them, and replace with a single merged interval.
Merging logic: find the first interval that ends >= left-1 and the last interval that starts <= right+1. Remove all intervals in between and create one merged interval from min(left, first.start) to max(right, last.end).
For count(): maintain a running total. When merging, subtract the lengths of removed intervals and add the length of the new merged interval. This avoids rescanning all intervals.
Visual walkthrough: add([2,3]): intervals = [[2,3]], count = 2. add([1,1]): intervals = [[1,1],[2,3]], count = 3. add([4,5]): intervals = [[1,1],[2,3],[4,5]], count = 5. add([2,4]): merge [2,3] and [4,5] -> [[1,1],[2,5]], count = 5.
Optimal Approach
Step 1: Maintain a sorted list of disjoint intervals and a running count.
Step 2: add(left, right):
- Find all intervals overlapping with [left, right].
- Remove them from the list and subtract their lengths from count.
- Create a new merged interval: start = min(left, first overlapping start), end = max(right, last overlapping end).
- Add the new interval and add its length to count.
Step 3: count(): return the running total.
Walkthrough:
- add([2,3]): no overlaps. Add [2,3]. count = 2.
- add([1,3]): overlaps [2,3]. Remove [2,3] (count -= 2). Merge -> [1,3]. Add [1,3] (count += 3). count = 3.
- add([4,5]): no overlaps. Add [4,5]. count = 5.
- add([2,5]): overlaps [1,3] and [4,5]. Remove both (count -= 3+2=5). Merge -> [1,5]. count += 5. count = 5.
Time: O(n) per add in the worst case (scanning and removing intervals). Space: O(n) for the interval list.
What Trips People Up in Real Interviews
Forgetting that intervals can merge across previously separate intervals. Adding [1,3] when [2,4] exists merges them into [1,4], not two separate intervals.
Not maintaining the sorted order. Without sorting, finding overlapping intervals requires scanning all intervals, making add() O(n) instead of O(log n) for the find + O(k) for the merge.
Using a segment tree when a simpler sorted-list approach works. Segment tree is overkill for this problem. A sorted list of disjoint intervals is simpler and efficient enough.
Counting integers incorrectly when intervals overlap. The count is the sum of unique positions covered, not the sum of interval lengths (which double-counts overlaps).
Off-by-one errors in interval merging. Use inclusive intervals: [left, right] means all integers from left to right inclusive. Length = right - left + 1.
Solution Code
class CountIntervals:
def __init__(self):
self.intervals = []
self.cnt = 0
def add(self, left, right):
new_l, new_r = left, right
merged = []
for l, r in self.intervals:
if r < left or l > right:
merged.append((l, r))
else:
new_l = min(new_l, l)
new_r = max(new_r, r)
merged.append((new_l, new_r))
merged.sort()
self.intervals = merged
self.cnt = sum(r - l + 1 for l, r in self.intervals)
def count(self):
return self.cntFrequently Asked Questions
What is the Count Integers in Intervals problem?
Design a data structure that counts the number of integers currently covered by at least one added interval. Implement the CountIntervals class with methods: add(left, right) adds the interval [left, right], and count() returns the total number of unique integers covered.
How do you solve Count Integers in Intervals?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Integers in Intervals?
Count Integers in Intervals is asked at Databricks. It is a hard difficulty problem.
What are common mistakes on Count Integers in Intervals?
- Forgetting that intervals can merge across previously separate intervals. Adding [1,3] when [2,4] exists merges them into [1,4], not two separate intervals.
- Not maintaining the sorted order. Without sorting, finding overlapping intervals requires scanning all intervals, making add() O(n) instead of O(log n) for the find + O(k) for the merge.
- Using a segment tree when a simpler sorted-list approach works. Segment tree is overkill for this problem. A sorted list of disjoint intervals is simpler and efficient enough.
- Counting integers incorrectly when intervals overlap. The count is the sum of unique positions covered, not the sum of interval lengths (which double-counts overlaps).
- Off-by-one errors in interval merging. Use inclusive intervals: [left, right] means all integers from left to right inclusive. Length = right - left + 1.