Interval Tree - Build an Interval Index and Query Overlapping Ranges

Question

## Problem

Implement an interval data structure that supports:

- `insert(start, end, value)` - add an interval.
- `query(point) -> List` - return all intervals containing `point`.
- `overlapping(start, end) -> List` - return all intervals overlapping `[start, end]`.
- `delete(start, end)` - remove the interval.

```python
class IntervalTree:
    def insert(self, start: int, end: int, value: any): ...
    def query(self, point: int) -> List: ...
    def overlapping(self, start: int, end: int) -> List: ...
    def delete(self, start: int, end: int): ...
```

**Example:**
```
tree = IntervalTree()
tree.insert(1, 5, "A")
tree.insert(3, 8, "B")
tree.insert(6, 9, "C")
tree.query(4)          -> ["A", "B"]   # both contain point 4
tree.overlapping(5, 7) -> ["A", "B", "C"]  # all overlap [5,7]
tree.delete(3, 8)
tree.query(4)          -> ["A"]
```

## Approach

Augmented BST: each node stores an interval; each subtree tracks the max endpoint. A `query(point)` traverses left if left subtree's max >= point.

## Follow-ups

1. What is the time complexity of `query` and `overlapping` in the worst case?
2. How does the augmented BST approach compare to a segment tree for this use case?
3. How would you handle intervals with the same `start` and `end` but different values?
4. Describe a real-world use case for an interval tree in systems programming.

Interval Tree - Build an Interval Index and Query Overlapping Ranges

Question Details

Full Details

Topics

More from LinkedIn