# LeetCode 715: Range Module

## Problem Restatement

We need to design a data structure called `RangeModule`.

It tracks ranges of numbers.

Each range is represented as a half-open interval:

```python
[left, right)
```

This means the interval includes `left`, but does not include `right`.

The data structure must support three operations:

| Operation | Meaning |
|---|---|
| `addRange(left, right)` | Start tracking every number in `[left, right)` |
| `queryRange(left, right)` | Return whether every number in `[left, right)` is tracked |
| `removeRange(left, right)` | Stop tracking every number in `[left, right)` |

The intervals may overlap, merge, or split.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `RangeModule()` | None | Creates an empty module |
| `addRange(left, right)` | Two integers | None |
| `queryRange(left, right)` | Two integers | Boolean |
| `removeRange(left, right)` | Two integers | None |

Important constraints:

| Constraint | Meaning |
|---|---|
| `1 <= left < right <= 10^9` | Large coordinate range |
| At most `10^4` calls | We need efficient operations |
| Intervals are half-open | `[left, right)` excludes `right` |

The class shape is:

```python
class RangeModule:

    def __init__(self):
        ...

    def addRange(self, left: int, right: int) -> None:
        ...

    def queryRange(self, left: int, right: int) -> bool:
        ...

    def removeRange(self, left: int, right: int) -> None:
        ...
```

## Examples

Example:

```python
rangeModule = RangeModule()
rangeModule.addRange(10, 20)
rangeModule.removeRange(14, 16)
rangeModule.queryRange(10, 14)
rangeModule.queryRange(13, 15)
rangeModule.queryRange(16, 17)
```

After adding `[10, 20)`, the tracked interval is:

```python
[10, 20)
```

After removing `[14, 16)`, the tracked intervals become:

```python
[10, 14)
[16, 20)
```

Now:

| Query | Result | Why |
|---|---|---|
| `[10, 14)` | `True` | Fully covered |
| `[13, 15)` | `False` | The part `[14, 15)` was removed |
| `[16, 17)` | `True` | Fully covered |

## First Thought: Track Every Number

A simple idea is to store every tracked number in a set.

For `addRange(left, right)`, insert every integer from `left` to `right - 1`.

For `removeRange(left, right)`, remove every integer from `left` to `right - 1`.

For `queryRange(left, right)`, check every integer from `left` to `right - 1`.

This fails for two reasons.

First, the range can go up to `10^9`.

Second, the problem describes real numbers in the interval, not only integers. We should track intervals, not individual points.

## Key Insight

Store a sorted list of disjoint tracked intervals.

For example, after some operations, we may store:

```python
[(10, 14), (16, 20), (30, 40)]
```

The invariant is:

1. Intervals are sorted by start.
2. Intervals do not overlap.
3. Adjacent or overlapping intervals are merged.

With this representation:

- `addRange` merges overlapping intervals.
- `removeRange` cuts overlapping intervals.
- `queryRange` checks whether one stored interval fully covers the query.

Because there are at most `10^4` operations, a sorted list is simple and accepted in Python.

## Algorithm: Add Range

To add `[left, right)`:

1. Create an empty list `new_intervals`.
2. Scan every existing interval `(start, end)`.
3. If the interval ends before `left`, keep it.
4. If the interval starts after `right`, insert the merged new interval once, then keep the rest.
5. If the interval overlaps `[left, right)`, merge it by updating:
   - `left = min(left, start)`
   - `right = max(right, end)`
6. At the end, insert the merged interval if it has not been inserted yet.

Overlapping intervals become one larger tracked interval.

## Algorithm: Query Range

To query `[left, right)`:

1. Find the interval whose start is the greatest start less than or equal to `left`.
2. Check whether that interval ends at or after `right`.

If such an interval exists, then the whole query range is tracked.

Otherwise, some part is missing.

## Algorithm: Remove Range

To remove `[left, right)`:

1. Create an empty list `new_intervals`.
2. Scan every existing interval `(start, end)`.
3. If it does not overlap `[left, right)`, keep it unchanged.
4. If it overlaps:
   - Keep the left leftover `[start, left)` if `start < left`.
   - Keep the right leftover `[right, end)` if `right < end`.
5. Replace the interval list.

Removing a range may split one interval into two.

## Correctness

The data structure stores exactly the tracked set as a sorted list of disjoint half-open intervals.

For `addRange`, every interval that does not overlap the added range remains unchanged. Every interval that overlaps the added range is merged into one interval whose boundaries are the minimum left endpoint and maximum right endpoint of all overlapping parts. Therefore the new interval covers exactly the old tracked values plus every value in `[left, right)`, with no gaps inside the merged region.

For `queryRange`, the query can be fully tracked only if one stored disjoint interval contains it. Since the stored intervals are sorted and non-overlapping, it is sufficient to check the interval immediately before or at `left`. If that interval ends at or after `right`, every number in `[left, right)` is tracked. Otherwise, no other interval can cover the missing part beginning at `left`.

For `removeRange`, every non-overlapping interval remains tracked. For each overlapping interval, the algorithm removes the intersection with `[left, right)` and keeps only the portions before `left` and after `right`. These leftovers are exactly the parts that should remain tracked.

After each operation, the list remains sorted and disjoint. Therefore all operations preserve the correct representation of the tracked ranges.

## Complexity

Let `n` be the number of stored intervals.

| Operation | Time | Space | Why |
|---|---|---|---|
| `addRange` | `O(n)` | `O(n)` | Scan and rebuild interval list |
| `queryRange` | `O(log n)` | `O(1)` | Binary search by interval start |
| `removeRange` | `O(n)` | `O(n)` | Scan and rebuild interval list |

The coordinate range is large, but the number of stored intervals is bounded by the number of operations.

## Implementation

```python
from bisect import bisect_right

class RangeModule:

    def __init__(self):
        self.intervals = []

    def addRange(self, left: int, right: int) -> None:
        new_intervals = []
        placed = False

        for start, end in self.intervals:
            if end < left:
                new_intervals.append((start, end))
            elif right < start:
                if not placed:
                    new_intervals.append((left, right))
                    placed = True

                new_intervals.append((start, end))
            else:
                left = min(left, start)
                right = max(right, end)

        if not placed:
            new_intervals.append((left, right))

        self.intervals = new_intervals

    def queryRange(self, left: int, right: int) -> bool:
        starts = [start for start, _ in self.intervals]
        index = bisect_right(starts, left) - 1

        if index < 0:
            return False

        start, end = self.intervals[index]
        return start <= left and right <= end

    def removeRange(self, left: int, right: int) -> None:
        new_intervals = []

        for start, end in self.intervals:
            if end <= left or right <= start:
                new_intervals.append((start, end))
            else:
                if start < left:
                    new_intervals.append((start, left))

                if right < end:
                    new_intervals.append((right, end))

        self.intervals = new_intervals
```

## Code Explanation

The module stores disjoint intervals:

```python
self.intervals = []
```

In `addRange`, we rebuild the interval list.

If an old interval is completely before the new range, keep it:

```python
if end < left:
    new_intervals.append((start, end))
```

If an old interval is completely after the new range, place the new merged range before it:

```python
elif right < start:
    if not placed:
        new_intervals.append((left, right))
        placed = True
```

Otherwise, the two intervals overlap or touch, so merge them:

```python
else:
    left = min(left, start)
    right = max(right, end)
```

For `queryRange`, we find the interval with the largest start not greater than `left`:

```python
index = bisect_right(starts, left) - 1
```

Then we check whether it covers the full query:

```python
return start <= left and right <= end
```

For `removeRange`, if an interval does not overlap the removed range, keep it:

```python
if end <= left or right <= start:
    new_intervals.append((start, end))
```

If it overlaps, keep only the leftovers:

```python
if start < left:
    new_intervals.append((start, left))

if right < end:
    new_intervals.append((right, end))
```

## Half-Open Interval Details

The interval `[left, right)` includes `left` and excludes `right`.

This affects boundary checks.

These two intervals touch but do not overlap in real-number coverage:

```python
[10, 14)
[14, 20)
```

For tracking ranges, we may merge them into:

```python
[10, 20)
```

because their union has no gap.

For removal, if we remove:

```python
[14, 16)
```

from:

```python
[10, 20)
```

we keep:

```python
[10, 14)
[16, 20)
```

The point `14` is removed because it belongs to `[14, 16)`.

The point `16` remains because the removed interval excludes `16`.

## Testing

```python
def test_range_module():
    rm = RangeModule()

    rm.addRange(10, 20)
    rm.removeRange(14, 16)

    assert rm.queryRange(10, 14) is True
    assert rm.queryRange(13, 15) is False
    assert rm.queryRange(16, 17) is True

    rm = RangeModule()
    rm.addRange(10, 20)
    rm.addRange(15, 25)

    assert rm.queryRange(10, 25) is True
    assert rm.queryRange(20, 24) is True
    assert rm.queryRange(25, 26) is False

    rm.removeRange(12, 22)

    assert rm.queryRange(10, 12) is True
    assert rm.queryRange(12, 13) is False
    assert rm.queryRange(22, 25) is True

    rm = RangeModule()
    rm.addRange(1, 5)
    rm.addRange(5, 10)

    assert rm.queryRange(1, 10) is True

    print("all tests passed")

test_range_module()
```

Test coverage:

| Test | Why |
|---|---|
| Add then remove middle | Confirms interval splitting |
| Query fully covered range | Confirms true result |
| Query partially removed range | Confirms false result |
| Merge overlapping ranges | Confirms add behavior |
| Remove from merged range | Confirms leftover intervals |
| Touching intervals | Confirms half-open boundary handling |