2276. Count Integers in Intervals

Description

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.

 

Solutions

Solution: Segment Tree

• Time complexity: O(logn)
• Space complexity: O(n)

 

JavaScript

class Node {
  left = null;
  right = null;
  count = 0;
}

const CountIntervals = function () {
  this.root = new Node();
};

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
CountIntervals.prototype.add = function (left, right) {
  this.addInterval(this.root, 1, 10 ** 9, left, right);
};

CountIntervals.prototype.addInterval = function (node, left, right, intervalLeft, intervalRight) {
  if (left > intervalRight || right < intervalLeft) return node;

  if (!node) {
    node = new Node();
  }

  const interval = right - left + 1;

  if (node.count === interval) return node;

  if (left >= intervalLeft && right <= intervalRight) {
    node.count = interval;

    return node;
  }

  const mid = Math.floor((left + right) / 2);

  node.left = this.addInterval(node.left, left, mid, intervalLeft, intervalRight);
  node.right = this.addInterval(node.right, mid + 1, right, intervalLeft, intervalRight);
  node.count = (node.left?.count ?? 0) + (node.right?.count ?? 0);

  return node;
};

/**
 * @return {number}
 */
CountIntervals.prototype.count = function () {
  return this.root.count;
};

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