Range module: track, remove and query half-open ranges

Track a set of numbers as half-open ranges [left, right). Support adding a range, removing a range, and asking whether every number in a range is currently tracked. Overlapping and touching ranges merge; removing the middle of a range splits it.

Interface

Unless you agree on a different interface with the interviewer, assume:

• RangeModule() — tracks nothing.
• add_range(left: int, right: int) -> None — track every number in [left, right).
• remove_range(left: int, right: int) -> None — stop tracking every number in [left, right).
• query_range(left: int, right: int) -> bool — True if every number in [left, right) is tracked.

Example

add_range(10, 20)
remove_range(14, 16)       # tracked: [10, 14) and [16, 20)
query_range(10, 14)  ->  True
query_range(13, 15)  ->  False
query_range(16, 17)  ->  True
add_range(14, 15)          # tracked: [10, 15) and [16, 20)
query_range(10, 15)  ->  True
query_range(10, 16)  ->  False    # 15 is not tracked

Constraints

• 1 <= left < right <= 10^9.
• Up to 20,000 calls in total.

Clarifying questions

• Half-open on both add and remove?
• Do [1, 5) and [5, 8) merge into [1, 8)?
• Which call is most frequent?

What a strong answer covers

• A sorted list of disjoint intervals with binary search: add merges every overlapping or touching interval, remove trims and splits.
• Query is one binary search: find the interval containing left and check it reaches right.
• O(log n) query, O(k + log n) add and remove where k is the intervals touched (O(n) with list shifting); a balanced tree or segment tree if that matters.
• Tests at the boundaries: touching ranges, removing an exact range, removing past both ends.

Follow-ups

• Return the total length tracked.
• Return the first untracked number at or after x.
• Coordinates up to 10^18 and 10^6 calls: what changes?