715. Range Module

Description

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

A half-open interval [left, right) denotes all the real numbers x where left <= x < right.

Implement the RangeModule class:

• RangeModule() Initializes the object of the data structure.
• void addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
• boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
• void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).

 

Example 1:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

Explanation
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)

 

Constraints:

• 1 <= left < right <= 109
• At most 104 calls will be made to addRange, queryRange, and removeRange.

 

Solutions

Solution: Simulation

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

 

JavaScript

const RangeModule = function () {
  this.intervals = [];
};

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.addRange = function (left, right) {
  const n = this.intervals.length;
  const intervals = [];
  let index = 0;

  while (index < n && this.intervals[index].right < left) {
    intervals.push(this.intervals[index]);
    index += 1;
  }
  const interval = { left, right };

  while (index < n && this.intervals[index].left <= interval.right) {
    interval.left = Math.min(this.intervals[index].left, interval.left);
    interval.right = Math.max(this.intervals[index].right, interval.right);
    index += 1;
  }
  intervals.push(interval);

  while (index < n) {
    intervals.push(this.intervals[index]);
    index += 1;
  }
  this.intervals = intervals;
};

/**
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
RangeModule.prototype.queryRange = function (left, right) {
  let low = 0;
  let high = this.intervals.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const interval = this.intervals[mid];

    if (interval.left <= left && interval.right >= right) return true;

    interval.left > left ? (high = mid - 1) : (low = mid + 1);
  }
  return false;
};

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.removeRange = function (left, right) {
  const n = this.intervals.length;
  const intervals = [];
  let index = 0;

  if (index < n && this.intervals[index].left > right) return;

  while (index < n && this.intervals[index].right < left) {
    intervals.push(this.intervals[index]);
    index += 1;
  }

  if (index < n && this.intervals[index].left < left) {
    const intervalFirst = { left: this.intervals[index].left, right: left };

    intervals.push(intervalFirst);

    if (this.intervals[index].right > right) {
      const intervalSecond = { left: right, right: this.intervals[index].right };

      intervals.push(intervalSecond);
    }
    index += 1;
  }

  while (index < n && this.intervals[index].right <= right) index += 1;

  if (index < n && this.intervals[index].left < right) {
    intervals.push({ left: right, right: this.intervals[index].right });
    index += 1;
  }

  while (index < n) {
    intervals.push(this.intervals[index]);
    index += 1;
  }
  this.intervals = intervals;
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * var obj = new RangeModule()
 * obj.addRange(left,right)
 * var param_2 = obj.queryRange(left,right)
 * obj.removeRange(left,right)
 */