Count Integers in Intervals

Count Integers in Intervals

What is this problem about?

The "Count Integers in Intervals" interview question asks you to design a data structure that can dynamically add intervals $[left, right]$ and return the total number of unique integers covered by all added intervals. Intervals can overlap, so you must ensure that each integer is only counted once, regardless of how many intervals cover it.

Why is this asked in interviews?

This "Hard" difficulty problem is popular at Databricks, Uber, and Google because it tests efficiency in managing dynamic ranges. It evaluates a candidate's ability to handle overlapping intervals and maintain a global count without re-calculating everything from scratch. It is a classic example of where naive list storage fails, requiring more sophisticated data structures like a Balanced BST or a Segment Tree.

Algorithmic pattern used

This problem is best approached using the Disjoint Intervals or Ordered Set pattern. By maintaining a set of non-overlapping intervals, you can efficiently add a new interval by merging any existing intervals that overlap with it. Alternatively, a Dynamic Segment Tree with lazy propagation can be used to handle the range updates and queries in $O(\log N)$ time, where $N$ is the range of possible values ($10^9$).

Example explanation

Suppose we perform the following operations:

1. add(2, 5): Intervals: [[2, 5]]. Count: 4 (integers 2, 3, 4, 5).
2. add(7, 10): Intervals: [[2, 5], [7, 10]]. Count: 4 + 4 = 8.
3. add(4, 8): The interval [4, 8] overlaps with both.
   • Merges with [2, 5] to become [2, 8].
   • Merges with [7, 10] to become [2, 10].
   • New Intervals: [[2, 10]]. Count: 9 (integers 2 through 10).

Common mistakes candidates make

One major pitfall is trying to store every integer in a Hash Set, which will consume massive amounts of memory ($10^9$ integers). Another mistake is failing to remove old intervals from the data structure when they are merged into a larger one, leading to redundant checks. Some also struggle with the boundary conditions—for instance, forgetting that an interval $[2, 5]$ covers $5 - 2 + 1 = 4$ integers.

Interview preparation tip

When dealing with "Count" or "Sum" queries over potentially overlapping ranges, always think about merging intervals. Mastering the "merge intervals" logic—specifically how to find and remove overlapping segments in a sorted structure—is a key skill for high-level technical interviews.