LeetCode Solutions Blog

Count Integers in Intervals

Number: 2357

Difficulty: Hard

Paid? No

Problem Description

We are asked to design a data structure (CountIntervals) that starts with an empty set of intervals and supports two operations:

add(left, right): Insert an interval [left, right] into the set.
count(): Return the number of unique integers present across all intervals. Note that intervals may overlap, and overlapping intervals must be merged so that each integer is only counted once.

Key Insights

We can store the intervals in a sorted data structure ensuring the intervals are non-overlapping (merged).
On each add operation, we have to merge any intervals that overlap with the new interval.
Maintaining a running sum (or recomputing the total after each merge) allows the count operation to run in O(1) time.
Techniques include binary search (or an ordered set / TreeMap) to efficiently find overlapping intervals.

Space and Time Complexity

Time Complexity:

Adding an interval takes O(m + log n) time where m is the number of intervals merged and n is the number of disjoint intervals stored.
Getting the count takes O(1) time. Space Complexity: O(n) where n is the number of disjoint intervals maintained in the data structure.

Solution

We maintain a sorted list (or tree-based structure) of disjoint intervals and a variable to keep track of the total count of integers currently covered. When adding a new interval [left, right]:

Find all intervals in the structure that overlap with [left, right].
Remove these intervals and merge them with the new interval (update left = min(existing.left, left) and right = max(existing.right, right)).
Subtract the count of removed intervals from the total count.
Insert the merged interval and update the total count accordingly. This ensures that there are no overlaps in the maintained intervals and that the count is always correct.

The following implementations in Python, JavaScript, C++, and Java illustrate the approach with detailed comments.

Code Solutions

# Python Implementation

class CountIntervals:
    def __init__(self):
        # List to store non-overlapping intervals; each interval is represented as [left, right].
        self.intervals = []
        # Running total count of unique integers in intervals.
        self.total = 0

    def add(self, left: int, right: int) -> None:
        new_left, new_right = left, right
        new_intervals = []
        # Iterate over existing intervals
        for interval in self.intervals:
            # If current interval ends before new interval starts, no overlap.
            if interval[1] < new_left - 1:
                new_intervals.append(interval)
            # If current interval starts after new interval ends, no overlap.
            elif interval[0] > new_right + 1:
                new_intervals.append(interval)
            else:
                # There is an overlap: update the new interval boundaries.
                new_left = min(new_left, interval[0])
                new_right = max(new_right, interval[1])
                # Remove the overlapping interval from total count.
                self.total -= (interval[1] - interval[0] + 1)
        # Add the merged interval.
        new_intervals.append([new_left, new_right])
        # Update total with the merged interval.
        self.total += (new_right - new_left + 1)
        # Sort intervals by start for future add operations.
        self.intervals = sorted(new_intervals)

    def count(self) -> int:
        # Return the current total count.
        return self.total

# Example Test
# countIntervals = CountIntervals()
# countIntervals.add(2, 3)    # adds interval [2,3]
# countIntervals.add(7, 10)   # adds interval [7,10]
# print(countIntervals.count())  # outputs 6 (digits: 2, 3, 7, 8, 9, 10)
# countIntervals.add(5, 8)    # merges to become [5,10] and [2,3]
# print(countIntervals.count())  # outputs 8 (digits: 2,3,5,6,7,8,9,10)