Hack University
474/670

474. Range Module

Hard

Design a RangeModule class that keeps track of which parts of the number line are currently "tracked". Every range is half-open: [left, right) covers left and everything up to but not including right.

Implement three methods:

  • add_range(left, right) — start tracking every real number in [left, right), merging with anything already tracked.
  • query_range(left, right) — return True exactly when every number in [left, right) is currently tracked.
  • remove_range(left, right) — stop tracking every number in [left, right), splitting tracked ranges if needed.

Your program processes a sequence of these operations and reports the result of each query.

Example 1 on the number lineaddRange(10, 20) tracks one block; removeRange(14, 16) punches a half-open hole, leaving [10, 14) and [16, 20). Queries succeed only when their whole half-open range lies inside the gold coverage.
10141620tracked after add(10,20) + remove(14,16): [10,14) and [16,20)query(10,14) → truequery(13,15) → false (14…15 untracked)query(16,17) → true

Example 1:

Input: addRange(10, 20), removeRange(14, 16), queryRange(10, 14) → true, queryRange(13, 15) → false, queryRange(16, 17) → true, addRange(15, 17)

Output: [true, false, true]

Explanation: After tracking [10, 20) and removing [14, 16), the tracked set is [10, 14) and [16, 20). So [10, 14) is fully tracked, [13, 15) is not (14 and 14.5 are missing), and [16, 17) is fully tracked.

Example 2:

Input: addRange(1, 5), addRange(7, 10), queryRange(5, 7) → false, addRange(5, 7), queryRange(1, 10) → true

Output: [false, true]

Explanation: The gap [5, 7) is untracked at first, so the first query fails. Adding [5, 7) fuses the three pieces into one block [1, 10), so the second query succeeds.

Constraints:

  • 1 ≤ q ≤ 10⁴
  • 1 ≤ L < R ≤ 10⁹
  • Every operation is `add`, `remove`, or `query` with two integers.

Hints:

Keep the tracked set as a sorted list of disjoint, non-touching intervals. Every operation then only has to decide what happens to the handful of intervals that overlap [L, R).

Half-open ranges make merging exact: [1, 4) plus [4, 6) must become [1, 6), or a later query over [3, 5) will wrongly fail. Merge intervals that touch, not just ones that overlap.

A neat trick: store just the boundary points in one sorted array where even indices are starts and odd indices are ends. add/remove/query all become two binary searches plus a splice, and the parity of the insertion index tells you whether a point is inside a tracked range.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: addRange(10, 20), removeRange(14, 16), queryRange(10, 14), queryRange(13, 15), queryRange(16, 17), addRange(15, 17)

Expected output: [true, false, true]