Implement a Half-Open Interval Range Module
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Implement a Half-Open Interval Range Module
Implement a module that tracks subsets of the real-number line using half-open intervals `[left, right)`.
Process a sequence of operations:
- `("add", left, right)` starts tracking every point in `[left, right)`.
- `("remove", left, right)` stops tracking every point in `[left, right)`.
- `("query", left, right)` asks whether every point in `[left, right)` is currently tracked.
Return the Boolean results of the query operations in their original order.
## Function Contract
```python
def run_range_module(operations: list[tuple[str, int, int]]) -> list[bool]:
...
```
## Constraints
- `1 <= len(operations) <= 20_000`
- `0 <= left < right <= 10**9`
- Adjacent tracked intervals may be merged.
- Removing a range may shorten or split an existing tracked interval.
- A query is true only when one continuous tracked union covers its entire half-open range.
- The input contains only `"add"`, `"remove"`, and `"query"` operations.
## Example
```text
operations = [
("add", 10, 20),
("remove", 14, 16),
("query", 10, 14),
("query", 13, 15),
("query", 16, 17),
]
result = [True, False, True]
```
Quick Answer: Implement a range module over half-open intervals with add, remove, and full-coverage query operations. Handle merging adjacent ranges, splitting tracked ranges, large coordinates, and up to 20,000 mixed operations while returning query results in order.
Implement run_range_module(operations). Each operation is a three-string row [kind, left, right], with integer endpoints encoded as decimal strings. add tracks [left,right), remove stops tracking it, and query asks whether one continuous tracked union covers the whole range. Return query booleans in order. Adjacent tracked intervals may merge.
Constraints
- 1 <= len(operations) <= 20,000
- 0 <= left < right <= 1,000,000,000
- Kinds are add, remove, or query.
Examples
Input: ([["add","10","20"],["remove","14","16"],["query","10","14"],["query","13","15"],["query","16","17"]],)
Expected Output: [True, False, True]
Explanation: Removing the middle splits one interval.
Input: ([["query","1","2"]],)
Expected Output: [False]
Explanation: Nothing is tracked initially.
Hints
- Maintain sorted disjoint intervals.
- Removal may emit a left piece, a right piece, or both.