{x}
blog image

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.

 

Example 1:

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 <= 109
  • At most 105 calls in total will be made to add and count.
  • At least one call will be made to count.

Solution Explanation:

This problem requires designing a data structure to efficiently handle adding intervals and counting the total number of unique integers covered by these intervals. A segment tree is a suitable choice for this task.

Approach:

The solution uses a segment tree to represent the range [1, 109]. Each node in the tree corresponds to a sub-interval of this range. The v value of a node represents the number of integers covered by intervals within that sub-interval. The add value indicates whether the entire sub-interval is covered (1) or not (0).

add(left, right): This function adds the interval [left, right] to the set of intervals. It traverses the segment tree, updating the v and add values of nodes to reflect the new coverage.

count(): This function returns the total number of integers covered by all intervals. It simply returns the v value of the root node of the segment tree.

Time and Space Complexity Analysis:

Time Complexity:

  • add(left, right): O(log N), where N is the range of integers (109 in this case). The segment tree's height is log N, so adding an interval requires traversing at most a logarithmic number of nodes.
  • count(): O(1). The count is stored directly in the root node.

Space Complexity:

  • The space complexity is determined by the size of the segment tree. While the theoretical size is proportional to the range of integers, in practice, we only need to store nodes corresponding to intervals that actually have intervals added. Hence, in the worst case, space complexity is O(M log N), where M is the number of intervals added. However, if the added intervals are relatively sparse and don't overlap too extensively, the space used will be much less than this theoretical maximum.

Code Explanation (Python):

The Python code implements a Node class representing a node in the segment tree and a SegmentTree class managing the tree operations. The CountIntervals class uses the SegmentTree to handle interval additions and counting.

Node Class: Stores the interval bounds (l, r), midpoint (mid), covered integer count (v), and full coverage flag (add).

SegmentTree Class: Contains the modify (add interval), query (count integers), pushup (update node values after modifications), and pushdown (propagate updates down the tree) methods. pushdown is crucial for efficient update propagation.

CountIntervals Class: Wraps the SegmentTree, providing a simpler interface for adding intervals (add) and getting the count of covered integers (count).

Other language implementations (Java, C++, Go, TypeScript) follow similar principles, adapting the syntax and data structures to each language's specific features. The core algorithms remain consistent across all languages.