Solution: Range Module

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)$ includes all real numbers $n$ where $left\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)$ to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within $[left,~right)$ that are not already being tracked.

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

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

Constraints:

• $1 \leq$ left $<$ right $\leq 10^4$

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

Solution

Let’s look at the step-by-step implementation of the functions:

• Add Range(left, right): This function adds a new interval [left, right] to the list of intervals, merging it with any overlapping intervals.

  • If the new interval is completely outside the existing intervals:

    • Append the new interval to the end if it is to the right of all existing intervals.

    • Insert the new interval at the beginning if it is to the left of all existing intervals.

  • If the new interval overlaps with existing intervals:

    • Find the overlapping intervals using the check_intervals method.

    • Calculate the minimum start and maximum end of the overlapping intervals and the new interval to determine the new interval’s boundaries.

    • Replace the overlapping intervals with this newly merged interval to keep the list nonoverlapping.

• Remove Range(left, right): This function removes a given interval [left, right] from the list of intervals, splitting any overlapping intervals as needed.

  • Do nothing if no intervals exist or the removal range is outside the existing intervals.

  • Find the overlapping intervals using the check_intervals method.

  • For each overlapping interval:

    • If the interval starts before the removal range, create a new interval from the start to the beginning of the removal range.

    • If the interval ends after the removal range, create a new interval from the end of the removal range to the end of the interval.

  • Replace the overlapping intervals with the new ones excluding the removal range, keeping the list non-overlapping.

• Query Range(left, right): This function checks if any of the existing intervals fully cover a given interval [left, right].

  • If there are no intervals, return FALSE.

  • Find the overlapping intervals using the check_intervals method.

  • Verify the start and end boundaries to check if the range [left, right] is fully contained within one of the identified intervals.

• Check Intervals(left, right): This helper function identifies the indexes of intervals that overlap or touch a given interval [left, right].

  • Use a binary search-like approach with an initial mid-point mid that starts at half the list size.

  • While mid is greater than or equal to $1$

    • Increment min_range by mid if the end of the interval at min_range + mid - 1 is less than left.

    • Decrement max_range by mid if the start of the interval at max_range - mid + 1 is greater than right.

    • Halve mid to refine the search area.

  • Return the indexes min_range and max_range that mark the boundaries of the overlapping intervals.

Let’s look at the following illustration to get a better understanding of the solution: