LeetCode 2276 - Count Integers in Intervals

Difficulty: 🔴 Hard
Topics: Design, Segment Tree, Ordered Set

Solution

Problem Understanding

This problem asks us to design a data structure that dynamically maintains a collection of integer intervals and efficiently reports how many distinct integers are covered by at least one interval.

Initially, the interval set is empty. We must support two operations:

add(left, right), which inserts a new interval [left, right]
count(), which returns the total number of unique integers covered by all intervals added so far

The important detail is that overlapping integers must only be counted once. If multiple intervals cover the same integer, that integer still contributes only one to the final count.

For example, suppose we add [2,3] and [7,10]. The covered integers are:

{2, 3, 7, 8, 9, 10}

The total count is 6.

If we later add [5,8], some numbers overlap with [7,10]. The union becomes:

{2, 3, 5, 6, 7, 8, 9, 10}

Notice that 7 and 8 are not counted twice. The result becomes 8.

The constraints tell us a great deal about the intended solution.

The interval bounds can be as large as 10^9, which immediately rules out any solution that explicitly stores every integer in the intervals. Even a single interval like [1, 10^9] would be impossible to materialize in memory.

We also have up to 10^5 total operations. Since every add() call can involve very large ranges, we need something significantly more efficient than iterating over each number.

The key observation is that we care about interval unions, not individual elements. Instead of storing every integer, we should maintain a collection of non-overlapping merged intervals and track their total covered length.

Several edge cases are important:

Newly added intervals may overlap existing intervals partially.
A new interval may fully contain one or many previous intervals.
A new interval may be completely contained inside an existing interval.
Adjacent intervals such as [1,3] and [4,5] should merge because the integer ranges are continuous and inclusive.
Very large intervals like [1, 10^9] must be handled efficiently without enumerating values.

Approaches

Brute Force Approach

A naive approach would explicitly store every covered integer inside a hash set.

Whenever add(left, right) is called, we iterate through every integer from left to right and insert it into a set.

When count() is called, we simply return the size of the set.

This works because a set naturally removes duplicates. If an integer already exists, reinserting it changes nothing.

However, this approach is far too slow and memory intensive.

Consider an interval like [1, 10^9]. Iterating through one billion numbers for a single operation is impossible within constraints. The memory required would also be enormous.

We need a way to reason about ranges collectively rather than individual integers.

Optimal Approach, Ordered Set of Merged Intervals

The key insight is that we only care about the union of intervals.

Instead of storing individual numbers, we maintain a set of non-overlapping intervals that represent the merged coverage.

When a new interval arrives:

Find all existing intervals that overlap or touch it.
Merge them into one larger interval.
Remove the old overlapping intervals.
Insert the merged interval.
Update the total covered count incrementally.

This works because overlapping intervals contribute duplicate coverage, so merging them prevents double counting.

For example:

Existing intervals:

[2,3] [7,10]

Add:

[5,8]

Since [5,8] overlaps [7,10], we merge:

[5,10]

Final structure:

[2,3] [5,10]

The total count becomes:

2 + 6 = 8

We can implement this efficiently using a sorted structure keyed by interval starts.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(right - left) per add	O(total covered integers)	Explicitly stores every integer
Optimal	O(log n + k) per add	O(n)	Maintains merged disjoint intervals

Here, k is the number of overlapping intervals removed during merging.

Algorithm Walkthrough

We maintain two pieces of state:

A sorted collection of non-overlapping intervals.
A running integer total_count storing how many distinct integers are covered.

The intervals remain merged at all times.

Step 1: Initialize the Data Structure

Start with:

An empty interval collection
total_count = 0

Since there are no intervals initially, the count is zero.

Step 2: Add a New Interval

When add(left, right) is called, we first assume the new interval is:

[new_left, new_right] = [left, right]

We then search for intervals that overlap or touch this range.

Two intervals overlap if:

existing_right >= new_left - 1
AND
existing_left <= new_right + 1

The ±1 adjustment matters because intervals are inclusive. Adjacent intervals should merge.

Example:

[1,3] and [4,5]

Since 3 + 1 = 4, they form one continuous covered range.

Step 3: Merge Overlapping Intervals

For every overlapping interval:

Expand the merged range:

new_left = min(new_left, existing_left)
new_right = max(new_right, existing_right)

Remove the old interval from storage.
Subtract its contribution from total_count.

This avoids double counting.

Step 4: Insert the Final Merged Interval

After processing overlaps, insert the merged interval back into the structure.

Then add:

new_right - new_left + 1

to total_count.

The +1 exists because intervals are inclusive.

Example:

[5,10]

contains:

10 - 5 + 1 = 6

integers.

Step 5: Return the Count

The count() operation becomes trivial.

Simply return total_count.

Since we maintain the answer incrementally, no recomputation is needed.

Why it works

The invariant of the data structure is that all stored intervals are always disjoint and fully merged.

Whenever a new interval is added, every overlapping interval is absorbed into one larger interval. Since we subtract the size of removed intervals and add back the merged interval size exactly once, every integer contributes precisely one to total_count.

Thus, total_count always equals the number of distinct covered integers.

Python Solution

from bisect import bisect_left
from typing import List, Tuple

class CountIntervals:

    def __init__(self):
        self.intervals: List[Tuple[int, int]] = []
        self.total_count = 0

    def add(self, left: int, right: int) -> None:
        merged_left = left
        merged_right = right

        index = bisect_left(self.intervals, (left, -1))

        if index > 0 and self.intervals[index - 1][1] + 1 >= left:
            index -= 1

        remove_start = index

        while (
            index < len(self.intervals)
            and self.intervals[index][0] <= merged_right + 1
        ):
            current_left, current_right = self.intervals[index]

            merged_left = min(merged_left, current_left)
            merged_right = max(merged_right, current_right)

            self.total_count -= (
                current_right - current_left + 1
            )

            index += 1

        self.intervals[remove_start:index] = [
            (merged_left, merged_right)
        ]

        self.total_count += (
            merged_right - merged_left + 1
        )

    def count(self) -> int:
        return self.total_count

# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left, right)
# param_2 = obj.count()

The implementation stores intervals in sorted order by their starting point.

The bisect_left() call finds the insertion position for the new interval. Since an overlap could begin with the previous interval, we check one step backward.

The merging loop absorbs all overlapping intervals. Each removed interval has its covered size subtracted from total_count.

After merging finishes, we replace the overlapping slice with one merged interval. This keeps the interval list sorted and non-overlapping.

Because count() only returns the maintained total, it executes in constant time.

Go Solution

package main

import "sort"

type CountIntervals struct {
	intervals [][2]int
	total     int
}

func Constructor() CountIntervals {
	return CountIntervals{
		intervals: make([][2]int, 0),
		total:     0,
	}
}

func (this *CountIntervals) Add(left int, right int) {
	mergedLeft := left
	mergedRight := right

	index := sort.Search(
		len(this.intervals),
		func(i int) bool {
			return this.intervals[i][0] >= left
		},
	)

	if index > 0 &&
		this.intervals[index-1][1]+1 >= left {
		index--
	}

	removeStart := index

	for index < len(this.intervals) &&
		this.intervals[index][0] <= mergedRight+1 {

		current := this.intervals[index]
		currentLeft := current[0]
		currentRight := current[1]

		if currentLeft < mergedLeft {
			mergedLeft = currentLeft
		}

		if currentRight > mergedRight {
			mergedRight = currentRight
		}

		this.total -= (
			currentRight - currentLeft + 1
		)

		index++
	}

	newIntervals := make([][2]int, 0)

	newIntervals = append(
		newIntervals,
		this.intervals[:removeStart]...,
	)

	newIntervals = append(
		newIntervals,
		[2]int{mergedLeft, mergedRight},
	)

	newIntervals = append(
		newIntervals,
		this.intervals[index:]...,
	)

	this.intervals = newIntervals

	this.total += (
		mergedRight - mergedLeft + 1
	)
}

func (this *CountIntervals) Count() int {
	return this.total
}

/**
 * Your CountIntervals object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(left, right);
 * param_2 := obj.Count();
 */

The Go implementation follows the same logic as Python.

Since Go does not have built-in bisect support, we use sort.Search() for binary search.

Slice replacement is handled manually by constructing a new slice containing:

Intervals before overlap
The merged interval
Remaining intervals

Go uses int, which safely handles values up to 10^9 under standard 64-bit environments.

Worked Examples

Example 1

Operations:

add(2,3)
add(7,10)
count()
add(5,8)
count()

Step 1: `add(2,3)`

Intervals Before	New Interval	Intervals After	Total
`[]`	`[2,3]`	`[[2,3]]`	2

Covered integers:

{2,3}

Step 2: `add(7,10)`

No overlap exists.

Intervals Before	New Interval	Intervals After	Total
`[[2,3]]`	`[7,10]`	`[[2,3],[7,10]]`	6

Covered integers:

{2,3,7,8,9,10}

Step 3: `count()`

Returns:

Step 4: `add(5,8)`

Overlap occurs with [7,10].

Merge result:

[5,10]

Intervals Before	New Interval	Merged Result	Total
`[[2,3],[7,10]]`	`[5,8]`	`[[2,3],[5,10]]`	8

Covered integers:

{2,3,5,6,7,8,9,10}

Step 5: `count()`

Returns:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n + k) per `add()`	Binary search plus overlapping interval merges
Space	O(n)	Stores merged disjoint intervals

The binary search costs O(log n) to find the insertion point.

The merge process only touches overlapping intervals. Since intervals remain disjoint, each interval can only be removed a limited number of times across all operations.

The count() operation is O(1) because the result is maintained incrementally.

Test Cases

# Example case
obj = CountIntervals()
obj.add(2, 3)
obj.add(7, 10)
assert obj.count() == 6  # Example before merge

obj.add(5, 8)
assert obj.count() == 8  # Example after overlap merge

# Single interval
obj = CountIntervals()
obj.add(1, 1)
assert obj.count() == 1  # Single integer interval

# Fully overlapping interval
obj = CountIntervals()
obj.add(1, 10)
obj.add(3, 5)
assert obj.count() == 10  # Nested interval

# Partial overlap
obj = CountIntervals()
obj.add(1, 5)
obj.add(4, 8)
assert obj.count() == 8  # Overlap on boundary

# Adjacent intervals should merge
obj = CountIntervals()
obj.add(1, 3)
obj.add(4, 6)
assert obj.count() == 6  # Adjacent merge

# Multiple chained merges
obj = CountIntervals()
obj.add(1, 2)
obj.add(5, 6)
obj.add(3, 4)
assert obj.count() == 6  # Connects intervals together

# Large values
obj = CountIntervals()
obj.add(1, 10**9)
assert obj.count() == 10**9  # Maximum interval size

# Duplicate interval
obj = CountIntervals()
obj.add(2, 8)
obj.add(2, 8)
assert obj.count() == 7  # No double counting

# Disjoint intervals
obj = CountIntervals()
obj.add(1, 2)
obj.add(10, 12)
assert obj.count() == 5  # Separate regions

# Interval bridging two groups
obj = CountIntervals()
obj.add(1, 2)
obj.add(6, 8)
obj.add(3, 7)
assert obj.count() == 8  # Bridges both groups

Test	Why
Example case	Validates problem statement behavior
`[1,1]`	Smallest interval
Nested interval	Ensures containment works
Partial overlap	Verifies correct merging
Adjacent intervals	Confirms inclusive merge logic
Chained merge	Tests interval bridging
`[1,10^9]`	Validates large range handling
Duplicate interval	Prevents double counting
Disjoint intervals	Ensures separate regions remain
Bridge interval	Verifies multi-interval merge

Edge Cases

A New Interval Is Fully Contained Inside an Existing Interval

Suppose we already have:

[1,10]

and add:

[3,5]

A buggy implementation might accidentally increase the count even though no new integers are introduced.

Our implementation correctly detects overlap, merges into [1,10], subtracts the old contribution, and re-adds the same interval size. The total remains unchanged.

A New Interval Connects Multiple Existing Intervals

Consider:

[1,2]
[5,6]

Then add:

[3,5]

The new interval bridges previously separate groups into:

[1,6]

An incorrect implementation might merge only one side. Our merging loop continues until all overlapping intervals are absorbed, ensuring full correctness.

Extremely Large Ranges

Intervals can reach:

[1, 10^9]

A naive implementation storing every integer would immediately fail due to time and memory usage.

Our interval-based representation stores only boundaries, so even the largest interval uses constant additional memory and processes efficiently.

Adjacent Intervals

Because intervals are inclusive, these intervals:

[1,3]
[4,5]

represent a continuous integer range.

Without careful boundary handling, an implementation may incorrectly leave them separate.

Our overlap check uses +1, ensuring adjacent intervals merge into:

[1,5]

correctly.

LeetCode 2276 - Count Integers in Intervals

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach, Ordered Set of Merged Intervals

Algorithm Walkthrough

Step 1: Initialize the Data Structure

Step 2: Add a New Interval

Step 3: Merge Overlapping Intervals

Step 4: Insert the Final Merged Interval

Step 5: Return the Count

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: add(2,3)

Step 2: add(7,10)

Step 3: count()

Step 4: add(5,8)

Step 5: count()

Complexity Analysis

Test Cases

Edge Cases

A New Interval Is Fully Contained Inside an Existing Interval

A New Interval Connects Multiple Existing Intervals

Extremely Large Ranges

Adjacent Intervals

Step 1: `add(2,3)`

Step 2: `add(7,10)`

Step 3: `count()`

Step 4: `add(5,8)`

Step 5: `count()`