Range Module

Try to solve the Range Module problem.

Statement

Design a Range Module data structure that effectively tracks ranges of numbers using half-open intervals and allows querying these ranges. A half-open interval [left,right)[left, right) includes all real numbers nn where left≤n<rightleft\leq n <right.

Implement the RangeModule class with the following specifications:

  • Constructor(): Initializes a new instance of the data structure.

  • Add Range(): Adds the half-open interval [left, right)[left,~right) to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within [left, right)[left,~right) that are not already being tracked.

  • Query Range(): Returns true if every real number within the interval [left, right)[left,~right) is currently being tracked, and false otherwise.

  • Remove Range(): Removes tracking for every real number within the half-open interval [left, right)[left,~right).

Constraints:

  • 1≤1 \leq left << right ≤104\leq 10^4

  • At most, 10310^3 calls will be made to Add Range(), Query Range(), and Remove Range().

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.