HardDesignSegment TreeOrdered SetUpdated Sep 2026

2276. Count Integers in Intervals

Asked at Databricks

Difficulty

Hard

Time

O(n) per add in the worst case,

Space

O(n)

Pattern

Design

Companies

1

Problem

Design a class called CountIntervals that keeps a set of integer intervals and can answer how many distinct integers are covered.

Start with an empty set. The method add(left, right) inserts the interval [left, right], which means every integer x with left <= x <= right. The method count() returns how many different integers are covered by at least one interval. An integer covered by several intervals is still counted only once.

Intervals may overlap or touch, and add can be called many times. The ranges are huge (up to 10^9), so you cannot mark every integer one by one. The trick is to keep the intervals sorted and disjoint, merging them as you go, and to keep a running total of covered integers.

Count distinct covered integers

covered2378910012345After add(2,3) and add(7,10): 6 integers are covered.covered23567891001234567After add(5,8): 5 and 6 are new, so the count becomes 8.
Overlapping intervals share integers, but each integer is counted once.

Constraints

  • ●1 <= left <= right <= 10^9
  • ●At most 10^5 calls in total will be made to add and count.
  • ●At least one call will be made to count.

Examples

Example 1
Input["CountIntervals", "add", "add", "count", "add", "count"] [[], [2, 3], [7, 10], [], [5, 8], []]
Output[null, null, null, 6, null, 8]
WhyAfter adding [2,3] and [7,10] we cover 2,3,7,8,9,10 — that is 6 integers. Then [5,8] adds 5 and 6, and 7 and 8 were already covered, so the total grows to 8.
Example 2
Input["CountIntervals", "add", "add", "count"] [[], [1, 5], [3, 8], []]
Output[null, null, null, 8]
Why[1,5] covers 1..5. [3,8] overlaps it, and the union is [1,8], which holds 8 integers.
Example 3
Input["CountIntervals", "add", "add", "count"] [[], [1, 2], [3, 4], []]
Output[null, null, null, 4]
WhyThe two intervals touch but do not overlap. Together they cover 1,2,3,4 — 4 integers.

Asked At

1 companies
CompanyDifficulty
DatabricksHardView all Databricks questions →

How to Think About It

1

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.

2

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.

3

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.

4

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).

5

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.

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.

Keep intervals sorted and disjoint

intervals[2,3][7,10]01Before add(5,8): two disjoint intervals, count = 2 + 4= 6.intervalsoverlap [5,8][2,3][7,10]01Both intervals overlap [5,8], so both are removed andtheir lengths subtracted.intervals[2,10]0One merged interval [2,10] is added back, so count = 6- 6 + 9 = 8.new = [min(left, s), max(right, e)]count += len(new) - sum(len(removed))
Each add merges every overlapping interval into one, and the running count is updated by subtracting the old lengths and adding the new one.
ComplexityTime O(n) per add in the worst case, Space O(n)add scans and rewrites the list of disjoint intervals, while count just returns the running total.

What Trips People Up in Real Interviews

1

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.

2

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.

3

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.

4

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).

5

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

O(n) per add in the worst case, time
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.cnt

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) per add in the worst case, time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.