715. Range Module - Detailed Explanation

Problem Statement

You are asked to design a data structure that tracks ranges of numbers (represented as half‐open intervals [left, right)) and supports the following operations:

• addRange(left, right):
  Adds the half-open interval [left, right) to the module. After adding, any number within that interval should be considered “covered.” Overlapping or adjacent intervals should be merged.

• queryRange(left, right):
  Returns true if every number in the half-open interval [left, right) is currently covered by some added range(s); otherwise, returns false.

• removeRange(left, right):
  Removes all numbers in the half-open interval [left, right) from the module. This operation may partially cut through an existing interval, splitting it into two intervals if needed.

Constraints:

• The number of operations can be large (e.g., up to 10⁴).
• The range of the numbers (left and right values) can be up to 10⁹.
• It is important to implement the operations efficiently.

Example:

RangeModule rm = new RangeModule();
rm.addRange(10, 20);       // Adds the interval [10, 20)
rm.removeRange(14, 16);    // Removes the interval [14, 16), resulting in intervals [10, 14) and [16, 20)
rm.queryRange(10, 14);     // Returns true because [10, 14) is fully covered.
rm.queryRange(13, 15);     // Returns false because 14 is not covered.
rm.queryRange(16, 17);     // Returns true because [16, 17) is covered.

Hints

• Hint 1: Think about how to maintain a set of disjoint intervals that represent the union of all added ranges. This will help in merging overlapping intervals when adding and in efficiently checking coverage during queries.
• Hint 2: When performing operations (add or remove), you may need to find the correct insertion point quickly. Consider using binary search on a sorted list of intervals.
• Hint 3: For queries, all you need to do is check if there is an interval that completely covers the given range.

Approaches

There are two common strategies to implement a Range Module:

Approach 1: Sorted List of Intervals with Binary Search

Idea:
Maintain a sorted list (or array) of disjoint intervals. Each interval is represented as [start, end).

• addRange: Use binary search to find intervals overlapping with [left, right), merge them, and update the list.
• queryRange: Use binary search to locate the interval whose start is just before or equal to the query’s left, then check if that interval’s end is at least right.
• removeRange: Similar to addRange; find all intervals that overlap with [left, right) and adjust or split them as needed.

Why It Works:
By keeping the intervals disjoint and sorted, each operation can run efficiently by scanning only the intervals that are relevant to the current operation.

Approach 2: Balanced Binary Search Tree (BST) / TreeMap

Idea:
Use a BST (or Java’s TreeMap) keyed by the start of the intervals. The BST allows you to quickly find the closest interval for a given query and to update intervals during add and remove operations.

Why It Works:
This data structure efficiently supports insertion, deletion, and querying in logarithmic time. Many languages offer built-in trees or sorted maps that make this approach straightforward.

Python Code

Below is a Python implementation using a sorted list of intervals with binary search.