Count Integers in Intervals

Given an empty set of intervals, implement a data structure that can:

• Add an interval to the set of intervals.
• Count the number of integers that are present in at least one interval.

Implement the CountIntervals class:

• CountIntervals() Initializes the object with an empty set of intervals.
• void add(int left, int right) Adds the interval [left, right] to the set of intervals.
• int count() Returns the number of integers that are present in at least one interval.

Note that an interval [left, right] denotes all the integers x where left <= x <= right.

For example:

Input
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]

Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals.
countIntervals.add(2, 3);  // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count();    // return 6
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8);  // add [5, 8] to the set of intervals.
countIntervals.count();    // return 8
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 5 and 6 are present in the interval [5, 8].
                           // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
                           // the integers 9 and 10 are present in the interval [7, 10].

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.

class CountIntervals:

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

    def add(self, left: int, right: int) -> None:
        self.intervals.append((left, right))

    def count(self) -> int:
        merged_intervals = []
        self.intervals.sort()

        for interval in self.intervals:
            if not merged_intervals:
                merged_intervals.append(interval)
            else:
                last_interval = merged_intervals[-1]
                if interval[0] <= last_interval[1]:
                    merged_intervals[-1] = (last_interval[0], max(last_interval[1], interval[1]))
                else:
                    merged_intervals.append(interval)

        total_count = 0
        for interval in merged_intervals:
            total_count += (interval[1] - interval[0] + 1)
        return total_count


# Brute Force Solution - Time Limit Exceeded
class CountIntervalsBruteForce:

    def __init__(self):
        self.present = set()

    def add(self, left: int, right: int) -> None:
        for i in range(left, right + 1):
            self.present.add(i)

    def count(self) -> int:
        return len(self.present)


# Optimal Solution using Segment Tree
class CountIntervalsOptimal:

    def __init__(self):
        self.tree = {}
        self.count_ = 0

    def update(self, start, end, left, right, node):
        if node not in self.tree:
            self.tree[node] = [0, left, right]

        if self.tree[node][0] == self.tree[node][2] - self.tree[node][1] + 1:
            return

        if start <= left and right <= end:
            self.tree[node][0] = right - left + 1
            return

        mid = (left + right) // 2
        if left == right:
            return

        if node * 2 + 1 not in self.tree:
             self.tree[node * 2 + 1] = [0, left, mid]
        if node * 2 + 2 not in self.tree:
            self.tree[node * 2 + 2] = [0, mid + 1, right]

        if start <= mid:
            self.update(start, end, left, mid, node * 2 + 1)
        if end > mid:
            self.update(start, end, mid + 1, right, node * 2 + 2)

        self.tree[node][0] = self.tree[node * 2 + 1][0] + self.tree[node * 2 + 2][0]

    def add(self, left: int, right: int) -> None:
        self.update(left, right, 1, 10**9, 0)

    def count(self) -> int:
        return self.tree[0][0]



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

Brute Force Approach

1. Data Structure: Use a set to store all the integers present in the added intervals.
2. Add Operation: When adding an interval [left, right], iterate through all integers from left to right (inclusive) and add them to the set.
3. Count Operation: Return the size of the set, which represents the number of distinct integers present in the intervals.

Big O Analysis:

• Time Complexity:
  • add(left, right): O(right - left), because in the worst case, we iterate through every number between left and right.
  • count(): O(1), because we simply return the size of the set.
• Space Complexity:
  • O(N), where N is the number of distinct integers in all the intervals. In the worst case, this could be quite large.

Optimized Approach using Segment Tree

1. Data Structure: Implement a segment tree where each node represents an interval and stores the count of integers covered by that interval.
2. Add Operation: When adding an interval [left, right], traverse the segment tree to find the overlapping intervals and update the count in the tree nodes.
3. Count Operation: The root of the segment tree stores the total count of integers present in the intervals.

Big O Analysis:

• Time Complexity:
  • add(left, right): O(log N), where N is the range of possible integers (10^9 in this case). This is because we are traversing a segment tree, where each level reduces the search space by half.
  • count(): O(1), because the count is stored in the root of the segment tree.
• Space Complexity:
  • O(N), where N is the range of possible integers. This is because, in the worst case, the segment tree might need to store information for every possible integer in the range.

Edge Cases:

1. Overlapping Intervals: The segment tree handles overlapping intervals naturally during the add operation. When intervals overlap, the count in the corresponding nodes is updated to reflect the total coverage.
2. Large Range of Integers: The range of integers can be quite large (up to 10^9). The segment tree approach is designed to handle this by dividing the range into smaller intervals.
3. Empty Intervals: If an interval [left, right] is added where left > right, it's treated as an empty interval and no updates occur in the segment tree.
4. Multiple Add Operations: Repeated calls to the add operation will update the segment tree, ensuring that the count accurately reflects all the added intervals.

Example:

CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals.
countIntervals.add(2, 3);  // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count();    // return 6
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8);  // add [5, 8] to the set of intervals.
countIntervals.count();    // return 8
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 5 and 6 are present in the interval [5, 8].
                           // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
                           // the integers 9 and 10 are present in the interval [7, 10].