Calendar conflict checks, genome feature lookups, and "which reservations overlap this time window?" all need the same operation: given a query interval, find stored intervals that overlap it, while intervals keep being added and removed. An interval tree handles that dynamically.
Store intervals in a balanced BST keyed by start point. Each node also stores max_end: the largest end point anywhere in its subtree. That one extra field is what makes pruning possible.
class Node:
def __init__(self, lo, hi):
self.lo, self.hi, self.max_end = lo, hi, hi
self.left = self.right = None
def overlaps(a_lo, a_hi, b_lo, b_hi):
return a_lo < b_hi and b_lo < a_hi # half-open
def search_any(node, lo, hi):
while node:
if overlaps(node.lo, node.hi, lo, hi):
return node
if node.left and node.left.max_end > lo:
node = node.left
else:
node = node.right
return None
If the left subtree's max_end is at or before the query's start, nothing on the left can overlap, so go right. If it extends past the query start and nothing on the left overlaps, then nothing on the right can either, because every right-side interval starts even later. So one root-to-leaf path suffices to find an overlap: O(log n) in a balanced tree.
To report every overlapping interval, recurse into both children when allowed by max_end and by the query's end (skip the right subtree if its smallest start is past the query end). That costs O(log n + k) for k results.
On insert or delete, update max_end along the path, and during rotations (red-black or AVL), recompute it for the two rotated nodes from their children. That's why it's called an augmented tree: the extra field is maintainable in O(1) per rotation.
In a "design a booking system" interview, a simpler first step is often a sorted map checking only the predecessor and successor intervals for conflict. Mention the interval tree as the generalisation when overlaps are allowed and you need to list them.
Disclosure: from the makers of linkjob.ai, a real-time AI interview copilot.