LeetCode Solutions Blog

Count Integers in Intervals

Difficulty: Hard

Problem Description

Given an empty set of intervals, implement a data structure that can add an interval to the set and count the number of integers that are present in at least one interval.

Key Insights

Intervals can overlap, so we need to merge them when adding new intervals.
Efficiently counting the total number of unique integers across potentially overlapping intervals is crucial.
A sorted data structure can help keep track of intervals and facilitate merging.

Space and Time Complexity

Time Complexity: O(n log n) for adding intervals (due to merging), O(1) for counting. Space Complexity: O(n) for storing intervals.

Solution

The solution involves using a list to store the intervals. When adding a new interval, we will merge it with any existing overlapping intervals. This ensures that we maintain a compact representation of the intervals. To count the total number of unique integers, we simply sum the lengths of the merged intervals.

Code Solutions

class CountIntervals:
    def __init__(self):
        self.intervals = []

    def add(self, left: int, right: int) -> None:
        new_interval = [left, right]
        merged_intervals = []
        i = 0
        # Merge overlapping intervals
        while i < len(self.intervals) and self.intervals[i][1] < left:
            merged_intervals.append(self.intervals[i])
            i += 1
        while i < len(self.intervals) and self.intervals[i][0] <= right:
            new_interval[0] = min(new_interval[0], self.intervals[i][0])
            new_interval[1] = max(new_interval[1], self.intervals[i][1])
            i += 1
        merged_intervals.append(new_interval)
        while i < len(self.intervals):
            merged_intervals.append(self.intervals[i])
            i += 1
        self.intervals = merged_intervals

    def count(self) -> int:
        total_count = 0
        for left, right in self.intervals:
            total_count += right - left + 1
        return total_count